Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

On the possibility of an instance-based complexity theory.

Boaz Barak
Harvard University
April 15, 2019
Worst-case analysis of algorithms has been the central method of theoretical computer science for the last 60 years, leading to great discoveries in algorithm design and a beautiful theory of computational hardness. However, worst-case analysis can be sometimes too rigid, and lead to an discrepancy between the "real world" complexity of a problem and its theoretical analysis, as well as fail to shed light on theoretically fascinating questions arising in connections with statistical physics, machine learning, and other areas.

Collective Coin-Flipping Protocols and Influences of Coalitions

Hamed Hatami
University of McGill
April 8, 2019
The seminal result of Kahn, Kalai and Linial implies that a coalition of a small number of players can bias the outcome of a Boolean function with respect to the uniform measure. We extend this result to arbitrary product measures, by combining their argument with a completely different argument that handles very biased coordinates.

Fooling polytopes

Li-Yang Tan
Stanford University
April 1, 2019

We give a pseudorandom generator that fools $m$-facet polytopes over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot \mathrm{log}(n)$. The previous best seed length had superlinear dependence on $m$. An immediate consequence is a deterministic quasipolynomial time algorithm for approximating the number of solutions to any $\{0,1\}$-integer program. Joint work with Ryan O'Donnell and Rocco Servedio.

Factors of sparse polynomials: structural results and some algorithms

Shubhangi Saraf
Member, School of Mathematics
March 26, 2019
Are factors of sparse polynomials sparse? This is a really basic question and we are still quite far from understanding it in general.

    In this talk, I will discuss a recent result showing that this is in some sense true for multivariate polynomials when the polynomial has each variable appearing only with bounded degree. 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.

    On the Approximation Resistance of Balanced Linear Threshold Functions

    Aaron Potechin
    University of Chicago
    March 25, 2019
    Constraint satisfaction problems (CSPs) are a central topic of study in computer science. A fundamental question about CSPs is as follows. Given a CSP where each constraint has the form of some predicate P and almost all of the constraints can be satisfied, is there a randomized polynomial time algorithm which is guaranteed to do significantly better in expectation than a random assignment? If so, then we say that the predicate P is approximable. If not, then we say that P is approximation resistant.

    A Brief Tour of Proof Complexity: Lower Bounds and Open Problems

    Toniann Pitassi
    University of Toronto; Visiting Professor, School of Mathematics
    March 19, 2019

    I will give a tour of some of the key concepts and ideas in proof complexity. First, I will define all standard propositional proof systems using the sequent calculus which gives rise to a clean characterization of proofs as computationally limited two-player games. I will also define algebraic and semi-algebraic systems (SOS, IPS, Polynomial Calculus). 

    An Application of the Universality Theorem for Tverberg Partitions

    Imre Barany
    Renyi Institute, Hungary and UCL, London
    March 18, 2019

    We show that, as a consequence of a remarkable new result of
    Attila P\'or on universal Tverberg partitions, any large-enough set
    $P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon point
    has half-space depth at least $c_d \cdot |P|$, where $c_d \in (0, 1)$
    depends only on $d$. We then give an application of this result to
    computing weak $\eps$-nets by random sampling. Joint work with Nabil
    Mustafa.

    Halting problems for sandpiles and abelian networks

    Lionel Levine
    Cornell University; von Neumann Fellow
    March 12, 2019

    Will this procedure be finite or infinite? If finite, how long can it last? Bjorner, Lovasz, and Shor asked these questions in 1991 about the following procedure, which goes by the name “abelian sandpile”: Given a configuration of chips on the vertices of a finite directed graph, choose (however you like) a vertex with at least as many chips as out-neighbors, and send one chip from that vertex to each of its out-neighbors. Repeat, until there is no such vertex. 

    Near log-convexity of measured heat in (discrete) time and consequences

    Mert Saglam
    University of Washington
    March 11, 2019

    We answer a 1982 conjecture of Erd&‌#337;s and Simonovits about the growth of number of $k$-walks in a graph, which incidentally was studied earlier by Blakley and Dixon in 1966. We prove this conjecture in a more general setup than the earlier treatment, furthermore, through a refinement and strengthening of this inequality, we resolve two related open questions in complexity theory: the communication complexity of the $k$-Hamming distance is $\Omega(k \log k)$ and that consequently any property tester for k-linearity requires $\Omega(k \log k)$.

    Improved List-Decoding and Local List-Decoding Algorithms for Polynomial Codes

    Swastik Kopparty
    Rutgers University; Member, School of Mathematics
    March 5, 2019

    I will talk about a recent result showing that some well-studied polynomial-based error-correcting codes
    (Folded Reed-Solomon Codes and Multiplicity Codes) are "list-decodable upto capacity with constant
    list-size". 

    At its core, this is a statement about questions of the form: "Given some points in the plane,
    how many low degree univariate polynomials are such that their graphs pass through 10% of these points"? 

    This leads to list-decodable and locally list-decodable error-correcting codes with the best known parameters.