Lunch

Approximate Matchings in the Simultaneous Communication Model

Sanjeev Khanna, University of Pennsylvania

The maximum matching problem is among the most well-studied problems in combinatorial optimization with many applications. We consider the problem of computing an approximate matching in a distributed model of computation, called the simultaneous communication model. In this model, an input graph is partitioned across multiple machines and each machine simultaneously sends a summary of its input to a coordinator who then outputs an approximate matching. The goal is to minimize the amount of information that each machine needs to send about its input to the coordinator. We will start by showing that the matching problem does not admit compact summaries. We will then show that a simple assumption on how the graph is partitioned completely alters the tractability of the problem. We will also highlight implications of these results on the study of the matching problem in two other well-studied models of computation, namely the streaming model and the MapReduce model.

Poster Session

Proof Complexity Lower Bounds from Algebraic Circuit Complexity

Michael Forbes, University of Illinois at Urbana-Champaign

We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs, where proof-lines are circuits from restricted boolean circuit classes. Except one, all of the subsystems considered in this work can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity).

Joint work with Amir Shpilka, Iddo Tzameret, and Avi Wigderson

Approximation algoritms for planarization and related problems

Tasos Sidiropoulos, University of Illinois at Chicago

In the minimum planarization problem, given some n-vertex graph, the goal is to find a set of vertices of minimum cardinality whose removal leaves a planar graph. This is a fundamental problem in topological graph theory. We present a $\log^{O(1)} n$-approximation algorithm for this problem on general graphs with running time $n^{O(\log n/\log\log n)}$. We also obtain a $O(n^\eps)$-approximation with running time $n^{O(1/\eps)}$ for any arbitrarily small constant $\eps > 0$. Prior to our work, no non-trivial algorithm was known for this problem on general graphs, and the best known result even on graphs of bounded degree was a polynomial-factor approximation. As an immediate corollary, we also obtain improved approximation algorithms for the crossing number problem on graphs of bounded degree. Our algorithm introduces several new tools including an efficient grid-minor construction for apex graphs, and a new method for computing irrelevant vertices. Analogues of these tools were previously available only for exact algorithms. Our work gives efficient implementations of these ideas in the setting of approximation algorithms, which could be of independent interest.

On the Quantitative Hardness of the Closest Vector Problem

Huck Bennett, Northwestern University

We initiate a research program which examines the quantitative hardness of lattice problems, bringing together the highly active areas of lattice-based cryptography and fine-grained complexity. Our main result shows that for every \varepsilon > 0 and almost every p \in [1, \infty) (excluding p \in 2\mathbb{Z}) there is no 2^{(1 - \varepsilon)n}-time algorithm for the closest vector problem with respect to the \ell_p norm (\textrm{CVP}_p) unless the Strong Exponential Time Hypothesis (SETH) fails. This result comes tantalizingly close to settling the quantitative time complexity of the important special case of \textrm{CVP}_2 (i.e., CVP in the Euclidean norm) for which a 2^{n + o(n)}-time algorithm is known, and is necessary (but not sufficient) for ensuring the security of about-to-be-deployed lattice-based cryptosystems. If, for example, there existed a 2^{n/20}-time algorithm for CVP then these cryptosystems would be insecure in practice.

Based on joint work with Alexander Golovnev and Noah Stephens-Davidowitz. The paper is available at https://arxiv.org/abs/1704.03928.

Breakfast

Online algorithms: still in vogue with some new perspectives

Allan Borodin, University of Toronto

Online algorithms have been used implicitly for at least as long as there have been scheduling problems (i.e. centuries). More recently, the theoretical CS interest in online algorithms coincides (implicitly) with Graham's classic paper on the makespan scheduling problem and the start of the area of approximation algorithms. Beyond online applications where online algorithms are obviously required, online algorithms are usually ``conceptually simple'' and can often be extended to ``semi-online'' simple algorithms that have much improved performance, both theoretically and ``in practice''. We will discuss these algorithms with respect to applications such as bipartite matching, max-sat and posted price mechanisms. The larger topic is the study of the power and limitations of conceptually simple algorithms.

Set Cover in Sub-linear Time

Sepideh Mahabadi, Columbia University (-> TTIC)

Given access to a collection of $m$ sets over a ground set of $n$ elements, the classic set cover problem asks for the minimum number of sets in the collection that cover all the elements. We study this problem from the perspective of sub-linear algorithms, where the input can be accessed by querying either the ith element contained in a set, or the jth set containing an element. In this work, we present sub-linear algorithms for the set cover problem and show that they achieve almost tight query complexities.

This is a joint work with Piotr Indyk, Ronitt Rubinfeld, Ali Vakilian, and Anak Yodpinyanee.

Student Talks

Online Covering with Sum of lq-Norm Objective: Xiangkun Shen, University of Michigan

List-decoding homomorphism codes: Angela Wu, University of Chicago

Password Hashing and Graph Pebbling: Samson Zhou, Purdue University

Lunch

A (2-epsilon) Approximation Algorithm for k-cut in FPT time

Anupam Gupta, Carnegie Mellon University

In the k-cut problem, we want to break a graph into k components while cutting the fewest edges. This problem has n^{2k} time exact algorithms, and several 2-approximation algorithms. Moreover, getting a (2-epsilon)-approximation would refute the small-set expansion hypothesis. However, it still seems feasible to get a (1+epsilon)-approximation for the problem in f(k,epsilon)*poly(n) time.

In this talk we present progress towards this problem, showing how to get an approximation factor better than 2 in f(k)*poly(n) time.

Based on joint work with Euiwoong Lee and Jason Li.

Stochastic load balancing on unrelated machines

Viswanath Nagarajan, University of Michigan

We consider the unrelated machine scheduling problem when job processing-times are stochastic. We provide the first constant factor approximation algorithm for the setting where one wants a fixed assignment of jobs to machines so as to minimize the expected makespan. The identical machines special case has been well-understood for several years, but the problem was previously open even in the case of related machines. The main technical contribution is an efficiently computable lower bound via an exponential-sized LP, and its rounding.

This is joint work with A. Gupta, A. Kumar and X. Shen.

Linear Sketching for Functions over the Boolean Hypercube

Grigory Yaroslavtsev, Indiana University

In this talk I will describe a new study of linear sketching that focuses on understanding the power of linear sketches based on parities (i.e. over GF_2, the field of two elements, as compared to the previous work that uses real arithmetic). I will illustrate various properties of such sketches using Fourier-analytic methods and tools from communication complexity. In particular, linear sketching over GF_2 turns out to be closely related to Fourier sparsity with respect to Lp-norms. Moreover, it can be shown to be optimal in streaming and distributed settings for data generated according to the uniform distribution.

Joint work with Sampath Kannan (UPenn), Elchanan Mossel (MIT) and Swagato Sanyal (NUS). To appear in CCC'18.