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...
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...
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...
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...
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...
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|$...
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...
We answer a 1982 conjecture of Erdő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...
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".
The emerging theory of High-Dimensional Expansion suggests a
number of inherently different notions to quantify expansion of
simplicial complexes. We will talk about the notion of local
spectral expansion, that plays a key role in recent advances
in...
