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.
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.
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.
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.
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.