The Northwestern CS Theory group cumulatively had eight papers at conferences held as part of the ACM Federated Computing Research Conference(FCRC) 2019, which took place recently in Phoenix, AZ. We had two papers in COLT, four in EC, and one each in SPAA and STOC. Members of the group who attended include Professors Jason Hartline, Samir Khuller, Konstantin Makarychev, and Aravindan Vijayaraghavan, postdoc Xue Chen, PhD students Yiding Feng, Aleck Johnsen, Yingkai Li, and Aravind Reddy. Also in attendance were CS Prof. Jessica Hullman and Econ PhD student Modibo Camara.
Conference on Learning Theory(COLT):
TCS postdoc Xue Chen presented a joint paper “Active Regression via Linear-Sample Sparsification” with Eric Price (UT Austin). This paper gives an efficient algorithm with an optimal sample complexity for the classical problem of linear regression. Its techniques yield improved results for the non-linear sparse Fourier transform setting.
TCS Ph.D. student Yingkai Li presented a joint paper with Yining Wang (CMU) and Yuan Zhou (UIUC). The paper “Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits” obtained almost tight dependence on the time horizon for regret minimization in linear bandits. One of the main results is to show that there is an extra sqrt(log T) factor in the lower bound, revealing a regret scaling quite different from classical multi-armed bandits. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.
Economics and Computation(EC):
TCS Ph.D. alumnus Sam Taggart (Assist. Prof. Oberlin College) presented a joint paper with TCS Prof. Jason Hartline in the joint session of EC and STOC.
TCS Prof. Jason Hartline presented a joint paper with TCS Ph.D. student Aleck Johnsen, Dennis Nekipelov (UVA), and Onno Zoeter (Booking.com).
TCS Ph.D. student Yingkai Li presented a joint paper with TCS Prof. Jason Hartline and TCS Ph.D. student Yiding Feng.
TCS Ph.D. student Chenhao Zhang had a joint paper with Nick Gravin (Shanghai University of Finance and Economics), Yaonan Jin (Columbia University) and Pinyan Lu (Shanghai University of Finance and Economics). The paper “Optimal Budget-Feasible Mechanisms for Additive Valuations” obtained tight approximation guarantee for budget-feasible mechanisms with an additive buyer. The paper proposes two-stage mechanisms that composite price-posting schemes with a pruning mechanism which greedily excludes the items with low value-per-cost ratios. A tight 2-approximation against the Knapsack and a tight 3-approximation against the Fractional-Knapsack are obtained by the proposed randomized and deterministic mechanisms respectively. Link to Video.
Symposium on Parallelism in Algorithms and Architectures(SPAA):
TCS Prof. Samir Khuller had a joint paper with visiting TCS PhD student Sheng Yang(UMD), Mosharaf Chowdhury(UMich), Manish Purohit(Google), and Jie You(UMich). The paper “Near Optimal Coflow Scheduling in Networks” focuses on the coflow scheduling problem which studies scheduling and data communication inter and intra datacenters. The main result is a randomized 2 approximation algorithm, significantly improving prior work both in theory and in practice.
Symposium on the Theory of Computing(STOC):
TCS Prof. Konstantin Makarychev had a paper with Yury Makarychev(TTIC) and Ilya Razenshteyn (Microsoft Research). This paper, “Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering“, shows that the cost of the optimal solution for Euclidean k-means or k-medians clustering is preserved up to a factor of (1+ε) under a projection onto a random O(log(k/ε)/ε2)-dimensional subspace. For k-means, this result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan.