Talks will take place in Lawson B151. Note that Purdue is on EST time.
12:00-12:50 Light Lunch and Registration, Lawson Commons
12:50-1:00 Welcome Remarks, B151
1:00-1:45 Jelani Nelson, Harvard. Title: Recent Advances in Euclidean Dimensionality Reduction.
Abstract: We give an overview of some recent advances on dimensionality reduction in Euclidean space, with focus on the "Johnson-Lindenstrauss Transform" and related embeddings.
1:45-2:00 Break
2:00-2:30 Sepideh Mahabadi, TTIC. Title: Diversity Maximization over Large Data Sets.
Abstract: We consider efficient construction of "composable core-sets" for the task of diversity maximization. A core-set is a subset of the data set that is sufficient for approximating the solution to the whole data set. A composable core-set is a core-set with the composability property: given a collection of data sets, the union of the core-sets for all data sets in the collection, should be a core-set for the union of the data sets. Using composable core-sets one can obtain efficient solutions to a wide variety of massive data processing applications, such as streaming algorithms and map-reduce model of computation.
The notion of diversity can be captured using several measures such as "minimum pairwise distance" and "sum of pairwise distances". However, in this work, we focus on the "determinant maximization" problem which has recently gained a lot of interest for modeling diversity. We present algorithms that are simple to implement and achieve almost optimal approximation guarantee. We further show their effectiveness on standard data sets. This is a joint work with Piotr Indyk, Shayan Oveis Gharan, and Alireza Rezaei.
2:30-3:00 Grant Schoenebeck, University of Michigan. Title: Eliciting Expert Information without Verification.
Abstract: A central question of crowd-sourcing is how to elicit expertise from agents. This is even more difficult when answers cannot be directly verified. This talk will argue that information theory provides the “right way” to think about these problems. It will illustrate how information theoretic properties can directly translate into improved crowd-sourcing mechanisms in a variety of settings. (No information theory background will be assumed.)
3:00-5:00 Coffee + Poster Session, Lawson Commons
5:00-5:45 Ryan Williams, MIT. Title: Lower Bounds from Algorithm Design: A Progress Report.
Abstract: A few years ago, I proposed a program for proving lower bounds in circuit complexity that takes an algorithmic approach: we can use interesting algorithms for solving circuit satisfiability and related problems to prove limitations on the power of circuits. In this talk, I will give an overview of how the program works, report on the successes of this program so far, and outline open frontiers that have yet to be resolved.
5:45-6:00 Zihao Deng, Washington University in St. Louis. Title: Learning Low Energy Deep Neural Networks.
Abstract: We present a polynomial-time algorithm for PAC-learning of constant-depth neural networks that have constant energy complexity. The energy complexity of a neural network is the maximum number of gates that fire" (output 1) simultaneously over the input distribution. This is a biologically motivated class of neural networks that, moreover, is capable of efficiently representing decision trees. Therefore, as a corollary, we also obtain the rst polynomial-time PAC-learning algorithm for decision trees in the standard, distribution-free model. Our algorithm, which learns networks of hard-threshold gates without the assumption of a margin, departs substantially from the standard paradigms for learning neural networks. Our approach is based on an iterative approach to finding a subset of points t by common parameters, introduced by Charikar et al., combined with a new algorithm for solving a particular class of spherical optimization problems with some additional linear constraints. Joint with Jizhou Huang and Brendan Juba.
6:30 MTD Dinner Event, Lawson Commons
Talks will take place in Lawson 1142.
9:00-9:30 Breakfast, Lawson Commons
9:30-10:00 Konstantin Makarychev, Northwestern. Title: Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering.
Abstract: Consider an instance of Euclidean k-means or k-medians clustering. We show that the cost of the optimal solution is preserved up to a factor of (1+ε) under a projection onto a random O(log (k/ε) / ε^2)-dimensional subspace. Further, the cost of every clustering is preserved within (1+ε). More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean k-clustering with the distances raised to the p-th power for any constant p.
For k-means, our 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. Joint work with Yury Makarychev and Ilya Razenshteyn.
10:00-10:30 Niao He, UIUC. Title: Sample Complexities of Conditional Stochastic Optimization.
Abstract: We study a class of stochastic optimization involving conditional expectations, which finds a wide spectrum of applications, particularly in reinforcement learning and robust learning. We establish the sample complexities of a modified Sample Average Approximation (SAA) and a biased Stochastic Approximation (SA) for such problems, under various structural assumptions such as smoothness and error bound conditions. Our analysis shows that both modified SAA and biased SA achieve the same complexity bounds, and smoothness matters. This talk is based on joint work with Yifan Hu and Xin Chen from UIUC.
10:30-10:45 Tanima Chatterjee, University of Illinois at Chicago. Title: Removing partisan bias in redistricting: computational complexity meets the science of gerrymandering.
Abstract: Partisan gerrymandering is a major cause for voter disenfranchisement in United States. Recently, Stephanopoulos and McGhee in several papers introduced a new measure of partisan gerrymandering via the so-called "efficiency gap" that computes the absolute difference of wasted votes between two political parties in a two-party system; the measure was found legally convincing in a US appeals court in a case that claims that the legislative map of the state of Wisconsin was gerrymandered. In this talk, we formalize and provide theoretical and empirical algorithmic analyses of the computational problem of minimizing this measure. Joint with Bhaskar Dasgupta, Laura Palmieri, Zainab Al-qurashi, Anastasios Sidiropoulos.
10:45-11:15 Coffee Break
11:15 -12:00 Sofya Raskhodnikova, Boston University and Simons Institute. Title: Erasures vs. Errors in Property Testing and Local Decoding.
Abstract: Corruption in data can be in the form of erasures (missing data) or errors (wrong data). Erasure-resilient property testing (Dixit, Raskhodnikova, Thakurta, Varma '16) and tolerant property testing (Parnas, Ron, Rubinfeld '06) are two models of sublinear algorithms that account for the presence of erasures and errors in input data, respectively. We discuss the erasure-resilient model and what can and cannot be computed in it. We separate this model from tolerant testing by showing that some properties can be tested in the erasure-resilient model with query complexity independent of the input size n, but require n^{Omega(1)} queries to be tested tolerantly.
To prove the separation, we initiate the study of the role of erasures in local decoding. Local decoding in the presence of errors has been extensively studied, but has not been considered explicitly in the presence of erasures. Motivated by the application in property testing, we begin our investigation with local list decoding in the presence of erasures. We prove an analog of the famous result of Goldreich and Levin on local list decodability of the Hadamard code. Specifically, we show that the Hadamard code is locally list decodable in the presence of a constant fraction of erasures, arbitrary close to 1, with list sizes and query complexity better than in the Goldreich-Levin theorem. The main tool used in proving the separation in property testing is an approximate variant of a locally list decodable code that works against erasures. We conclude with some open questions on the general relationship between local decoding in the presence of errors and in the presence of erasures. Joint work with Noga Ron-Zewi (Haifa University) and Nithin Varma (Boston University).
12:00-1:30 Lunch, Lawson Commons
1:30-2:00 Ilya Volkovich, University of Michigan. Title: Factors of sparse polynomials: structural results and some algorithms.
Abstract: We study the problem of deterministic factorization of sparse polynomials. We show that if f is a polynomial in n variables with at most s terms and the individual degrees of its variables bounded by d, then f can be deterministically factored in time s^{O(\poly(d) log n)}.
Prior to our work, the only efficient factoring algorithms known for this class of polynomials were randomized, and other than for the cases of d=1 and d=2, only exponential time deterministic factoring algorithms were known. A crucial ingredient in our proof is a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular we show that the sparsity (i.e. the number of terms) of each factor of f is bounded by s^{O(d^2 logn)}. This is the first nontrivial bound on factor sparsity for d>2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem.
Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials. This is a joint work with Vishwas Bhargav and Shubhangi Saraf.
2:00-2:30 Aaron Potechin, University of Chicago. Title: Sum of Squares Lower Bounds from Symmetry and a Good Story.
Abstract: The sum of squares hierarchy is a hierarchy of semidefinite programs which has the three advantages of being broadly applicable, powerful, and in some sense, simple as all it uses are polynomial equalities and the fact that squares are non-negative over R. However, the sum of squares does have a few known weaknesses. One such weakness, as shown by Grigoriev's sum of squares lower bound on the knapsack problem, is that the sum of squares hierarchy is poor at capturing integrality arguments.
In this work, we further explore this weakness of the sum of squares hierarchy. Roughly speaking, we show that if the problem is symmetric and the difficulty of the problem comes from integrality arguments then we can automatically obtain a sum of squares lower bound. As a special case, we obtain a sum of squares lower bound for the following Turan type problem: Minimize the number of triangles in a graph of a given edge density.
In this talk, I will describe Goodman's bound for this triangle problem, the true answer to this triangle problem which was shown by Razborov in 2008, and how we can obtain pseudo-expectation values for this triangle problem. Note: This talk will not assume any familiarity with the sum of squares hierarchy.
2:30-3:00 Coffee Break
3:00-3:15 Nikolai Karpov, Indiana University, Bloomington. Title: Distributed and Streaming Linear Programming in Low Dimensions.
Abstract: We study linear programming and general LP-type problems in several big data (streaming and distributed) models. We mainly focus on low dimensional problems in which the number of constraints is much larger than the number of variables. Low dimensional LP-type problems appear frequently in various machine learning tasks such as robust regression, support vector machines, and core vector machines. In this work we give both upper and lower bounds for LP-type problems in distributed and streaming models. Our bounds are almost tight when the dimensionality of the problem is a fixed constant. Joint with Sepehr Assadi and Qin Zhang.
3:30-3:45 Yifeng Teng, University of Wisconsin Madison. Title: Reasonable multi-item mechanisms are not much better than item pricing,
Abstract: Multi-item mechanisms can be very complex offering many different bundles to the buyer that could even be randomized. Such complexity is thought to be necessary as the revenue gaps between randomized and deterministic mechanisms, or deterministic and simple mechanisms are huge even for additive valuations. We challenge this conventional belief by showing that these large gaps can only happen in unrealistic situations. These are situations where the mechanism overcharges a buyer for a bundle while selling individual items at much lower prices. Arguably this is impractical as the buyer can break his order into smaller pieces paying a much lower price overall. Our main result is that if the buyer is allowed to purchase as many (randomized) bundles as he pleases, the revenue of any multi-item mechanism is at most O(logn) times the revenue achievable by item pricing, where n is the number of items. This holds in the most general setting possible, with an arbitrarily correlated distribution of buyer types and arbitrary valuations. We also show that this result is tight in a very strong sense. Any family of mechanisms of subexponential description complexity cannot achieve better than logarithmic approximation even against the best deterministic mechanism and even for additive valuations. In contrast, item pricing that has linear description complexity matches this bound against randomized mechanisms. Joint with Shuchi Chawla and Christos Tzamos.
3:15-3:30 Akash Kumar, Purdue University. Title: Finding forbidden minors in Bounded degree graphs.
Abstract: Let G be an undirected, bounded degree graph with n vertices. Fix a finite graph H, and suppose one must remove \eps n edges from G to make it H-minor free (for some small constant \eps > 0). We give an n^{1/2 + o(1)}-time randomized procedure that, with high probability, finds an H-minor in such a graph. For an example application, suppose one must remove \eps n edges from a bounded degree graph G to make it planar. This result implies an algorithm, with the same running time, that produces a K_3,3 or K_5 minor in G. No sublinear time bound was known for this problem, prior to this result. By the graph minor theorem, we get an analogous result for any minor-closed property. Up to n^{o(1)} factors, this resolves a conjecture of Benjamini-Schramm-Shapira (STOC 2008) on the existence of one-sided property testers for minor-closed properties. Furthermore, our algorithm is nearly optimal, by an \Omega(\sqrt n) lower bound of Czumaj et al (RSA 2014). Prior to this work, the only graphs H for which non-trivial property testers were known for H-minor freeness are the following: H being a forest or a cycle (Czumaj et al, RSA 2014), K_2,k / the k-by-2-grid / and the k-circus (Fichtenberger et al, Arxiv 2017). Joint with C. Seshadhri and A. Stolman.