Category: News

Northwestern CS Theory group @ FCRC 2019

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.  The paper, “Sample Complexity for Non-truthful Mechanisms“, describes a family of winner-pays-bid and all-pay (i.e., non-truthful) mechanisms that can be optimized from past bid data from the same market.  Most mechanisms in practice are non-truthful and, for example, the winner-pays-bid format is especially common.  The literature on sample complexity in mechanism design is well established, however, this paper is the first to consider non-truthful mechanisms.

TCS Prof. Jason Hartline presented a joint paper with TCS Ph.D. student Aleck Johnsen, Dennis Nekipelov (UVA), and Onno Zoeter (Booking.com).  The paper, “Dashboard Mechanisms for Online Marketplaces” gives a theoretical model for how a bidding dashboard can both make it easier for bidders in an online marketplace to optimize their bids and for the designer to optimize the mechanism.  A key idea in the paper is that if bidders optimize their bids for the dashboard, which predicts the outcome that will be obtained for any bid, then the underlying preferences of the bidders can be easily inferred from the bids.  Link to Video.

TCS Ph.D. student Yingkai Li presented a joint paper with TCS Prof. Jason Hartline and TCS Ph.D. student Yiding Feng.  The paper, “Optimal Auctions vs. Anonymous Pricing: Beyond Linear Utility“, introduces a approximation framework which approximately reduces the analysis of anonymous pricing for agents with non-linear utility to agents with linear utility in revenue-maximization. Applying this framework, constant approximation guarantee of anonymous pricing is shown for agents with public-budget utility, private-budget utility, and (a special case of) risk-averse utility.  A key idea in the paper is to define a parameterization of the regularity property that extends to agents with non-linear utility. Link to Video.

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.

Two Northwestern papers in FOCS 2015 (with video)

Talk videos are online from the 2015 Symposium on Foundations of Computer Science (FOCS).  The CS Theory group had two papers at the conference.

meNorthwestern CS Theory and Economics Ph.D. student Manolis Pountourakis did a really fantastic job of presenting his paper Optimal Auctions vs. Anonymous Pricing (joint with with coauthors Saeed Alaei, Rad Niazadeh, Yang Yuan, and me). The paper proves that eBay’s Auctions and Buy-It-Now (posted pricings) are within at least an e = 2.718 factor of the revenue optimal auction (which may be asymmetric and very complicated). This is a worst-case bound that is quite difficult to prove; in practice the eBay’s sales mechanisms likely do much better.  Watch the video!

dsc-mTCS Prof. Anindya De presented his paper Beyond the central limit theorem: Asymptotic expansions and pseudorandomness for combinatorial sums. This paper extends the central limit theorem to achieve faster convergence rates by using information about a large number of moments of the sum (as opposed to just the mean and variance). This result also has applications in space bounded derandomization, a central question in complexity theory.  Watch the video!

Northwestern CS initiates the Quarterly Theory Workshop

The Northwestern CS Theory Group hosted its First Quarterly Theory Workshop last month on the theme of Algorithmic Game Theory and Data Science. Fantastic talks were given by workshop speakers Tim Roughgarden (Stanford), Avrim Blum (CMU), and Eva Tardos (Cornell). Videos of the talks are available on the workshop webpage.

The goal of this new quarterly theory workshop format is to facilitate a deep discussion of the workshop theme and enable broad participation from theoretical computer science faculty and students in the greater Chicago area. For this first workshop, we were especially delighted to have attendees coming from the Toyota Technology Institute, University of Illinois at Chicago, the University of Chicago, and the University of Wisconsin at Madison. A colleague wrote afterward: “Thank you so much for inviting my students to attend the workshop yesterday! They were all blown away by the experience.”

The Second Quarterly Theory Workshop will be held on the morning of May 17 (Tuesday) on the theme of semidefinite programming hierarchies and sum-of-squares. The speakers are Boaz Barak (Harvard), David Steurer (Cornell), and Prasad Raghavendra (UC-Berkeley). The workshop will be preceded, on the morning of May 16 (Monday), by a tutorial on sum-of-squares by Madhur Tulsiani (TTI-Chicago). Individual meetings with the speakers are available on Monday and Tuesday afternoon.

Thanks to everyone who came and made the first workshop a success, we hope to see you all again for the second!

Ph.D. Nima Haghpanah to join Economics at Penn State

nimaCongratulations to former Northwestern CS Economics and Theory Ph.D. student Nima Haghpanah for accepting a tenure track assistant professorship at the Economics Department at Pennsylvania State! Nima’s Ph.D. dissertation, titled Optimal Multi-parameter Auction Design, won Northwestern’s CS dissertation award in 2015. It revisits four of the main conclusions of Roger Myerson’s 1981 paper, also award winning, and extends or approximately extends them to environments where the bidders have multi-dimensional preferences. Multi-dimensional auction design is well regarded as one of the most impenetrable areas for economic analysis. Nima made progress on this problem by deftly combining analysis methods from both economics and theoretical computer science.

When I joined Northwestern in 2008, at the time with Lance Fortnow and Nicole Immorlica, our goal was to create a program where the next generation of Ph.D.s in algorithmic game theory could train to become equal parts economists and computer scientists. In addition to the usual courses taken by theoretical computer scientists, the first-year students in the program take the introductory Ph.D. course sequences in microeconomics, game theory, and optimization that are taught in Northwestern’s Economics Department and Kellogg School of Management. The most important part of the program, however, is the outstanding students who have joined us, made it a fantastic and collegial environment, and have done really amazing research. Thanks, Nima, for helping us all achieve our goals. We look forward to seeing even more amazing things come from you at Penn State!