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...
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...
A matroid is an abstract combinatorial object which generalizes
the notions of spanning trees, and linearly independent sets of
vectors. I will talk about an efficient algorithm based on the
Markov Chain Monte Carlo technique to approximately...
Lorentzian polynomials link continuous convex analysis and
discrete convex analysis via tropical geometry. The class of
Lorentzian polynomials contains homogeneous stable polynomials as
well as volume polynomials of convex bodies and projective...
One of the major goals of complexity theory is to prove lower
bounds for various models of computation. The theory often proceeds
in buckets of three steps. The first is to come up with a
collection of techniques. The second is to be frustrated at...
