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...
A linear matrix is a matrix whose entries are linear forms in
some indeterminates $t_1,\dots, t_m$ with coefficients in some
field $F$. The commutative rank of a linear matrix is
obtained by interpreting it as a matrix with entries in the
function...
Randomness dispersers are an important tool in the theory of
pseudorandomness, with numerous applications. In this talk, we will
consider one-bit strong dispersers and show their connection to
erasure list-decodable codes and Ramsey graphs.
