Columbia Theory Seminar, Spring 2019

For Spring 2019 the usual time for the meetings will be Fridays at 13:00 in the CS Conference Room (453 CSB). Abstracts for talks are given below the talk schedule.

Talk Abstracts

Friday, January 25:
The Greedy Algorithm is Not Optimal for On-line Edge Coloring
David Wajc
Carnegie Mellon University

Abstract: The classic edge coloring problem asks to partition the edges of a graph into as few matchings (colors) as possible. By Vizing's theorem, any graph of maximum degree Δ can be edge colored using Δ+1 colors (in polynomial time). However, in many applications of edge coloring the graph is not entirely known in advance, making the problem harder. Motivated by such applications, we study edge coloring in the online adversarial vertex arrival model of Karp, Vazirani and Vazirani. Under such adversarial arrivals, a 1992 paper of Bar-Noy, Naor and Motwani, titled simply "The greedy algorithm is optimal for on-line edge coloring", proves the optimality of the trivial greedy algorithm, which on graphs with maximum degree Δ requires 2Δ-1 colors. However, their online lower bound requires Δ=O(log n), and they conjectured the existence of better algorithms than greedy for Δ large enough. We resolve this conjecture positively for bipartite graphs with Δ=ω(logn), and present optimal algorithms (up to o(1) terms) for such graphs. Moreover, we show a surprising dichotomy between the setting where Δ is known apriori and when this crucial parameter is unknown, and present optimal bounds for both known and unknown Δ scenarios.

Joint work with Ilan Reuven Cohen and Binghui Peng.

Friday, February 1:
Adventures in Monotone Complexity and TFNP
Mika Göös
Institute for Advanced Study

Abstract: *Separations:* We introduce a monotone variant of XOR-SAT and show it has exponential monotone circuit complexity. Since XOR-SAT is in NC^2, this improves qualitatively on the monotone vs. non-monotone separation of Tardos (1988). We also show that monotone span programs over R can be exponentially more powerful than over finite fields. These results can be interpreted as separating subclasses of TFNP in communication complexity.

*Characterizations:* We show that the communication (resp. query) analogue of PPA (subclass of TFNP) captures span programs over F_2 (resp. Nullstellensatz degree over F_2). Previously, it was known that communication FP captures formulas (Karchmer--Wigderson, 1988) and that communication PLS captures circuits (Razborov, 1995).

Joint work with Pritish Kamath, Robert Robere, and Dmitry Sokolov.

Friday, February 8:
Bloom Filters, Adaptivity, and the Dictionary Problem
Michael A. Bender
Stony Brook University

Abstract: A Bloom filter (or alternative) maintains a compact, probabilistic representation of a set S of keys from a universe U. The price of being small is that there is a (bounded) probability of false positives.

This talk presets alternatives to Bloom filters that are faster, more space efficient, and support a wider range of operations. We show how these filters can adapt based on the results of past queries.

Joint work with Mayank Goswami, Sam McCauley, Martin Farach-Colton, Rob Johnson, and Shikha Singh.

Friday, February 15:
Factors of sparse polynomials: structural results and some algorithms
Shubhangi Saraf
Rutgers University

Abstract: 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 when the polynomial has each variable appearing only with bounded degree. In particular we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s^{O(d^2 logn)}. This is the first nontrivial bound on factor sparsity for any value of d which is more than 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.

Using our sparsity bound, we then show how to devise efficient (quasi polynomial time) deterministic factoring algorithms for sparse polynomials of bounded individual degree. 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.

The talk is based on joint work with Vishwas Bhargav and Ilya Volkovich.

Thursday, February 21:
Static Data Structure Lower Bounds Imply Rigidity
Sasha Golovnev
Harvard University

Abstract: We show that static data structure lower bounds in the group (linear) model imply semiexplicit lower bounds on matrix rigidity. In particular, we prove that an explicit lower bound of t > omega(log^2 n) on the cell-probe complexity of linear data structures in the group model, even against arbitrarily small linear space (s = (1 + eps)n), would already imply a semi-explicit (P^NP) construction of rigid matrices with significantly better parameters than the current state of art (Alon, Panigrahy and Yekhanin, 2009). Our results further assert that polynomial (t >= n^delta) data structure lower bounds against near-optimal space, would imply super-linear circuit lower bounds for log-depth linear circuits (a four-decade open question). In the succinct space regime (s = n + o(n)), we show that any improvement on current cell-probe lower bounds in the linear model would also imply new rigidity bounds. Our results rely on a new connection between the "inner" and "outer" dimensions of a matrix (Paturi and Pudlak, 2006), and on a new reduction from worst-case to average-case rigidity, which is of independent interest.

Joint work with Zeev Dvir and Omri Weinstein.

Contact Alexandr Andoni, Omri Weinstein, or Timothy Sun if you want to volunteer to give a talk (especially students!). The talk can be about your or others' work. It can be anything from a polished presentation of a completed result, to an informal black-board presentation of an interesting topic. It should be accessible to a general theory audience. Alex will be happy to help students choose papers to talk about.
There is a mailing list for the reading group. General information about the mailing list (including how to subscribe yourself to it) is available here.
Back to Theory of Computation at Columbia.