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.
Given an arbitrary graph, we show that if we are allowed to
modify (say) 1% of the edges then it is possible to obtain a much
smaller regular partition than in Szemeredi's original proof of the
regularity lemma. Moreover, we show that it is...
In this talk, I will give an overview on how PCPs, combined with
cryptographic tools, are used to generate succinct and efficiently
verifiable proofs for the correctness of computations. I will focus
on constructing (computationally sound)...
What is the largest number of projections onto k coordinates
guaranteed in every family of m binary vectors of length n? This
fundamental question is intimately connected to important topics
and results in combinatorics and computer science (Turan...
Tensor networks describe high-dimensional tensors as the
contraction of a network (or graph) of low-dimensional tensors.
Many interesting tensor can be succinctly represented in this
fashion -- from many-body ground states in quantum physics to
the...
