I'll present a new algorithm to refute, that is, efficiently
find certificates of unsatisfiability, for smoothed instances of
k-SAT and other CSPs. Smoothed instances are produced by starting
with a worst-case instance and flipping each literal in...
This talk will serve as an introduction to the random algebraic
method. This method has its origins in the following problem:
suppose the binomial random graph comes "close" to having some
property of interest P, but fails to do so because of the...
The degree mantra states that any non-zero univariate polynomial
of degree at most d has at most d roots (counted with
multiplicity). A generalization of this to the multivariate
setting, proved by Dvir-Kopparty-Saraf-Sudan asserts that over
any...
Reproducibility is vital to ensuring scientific conclusions are
reliable, but failures of reproducibility have been a major issue
in nearly all scientific areas of study in recent decades. A key
issue underlying the reproducibility crisis is the...
Consider the action of a group on a finite-dimensional vector
space. Given some natural conditions on the group, Hilbert showed a
famous "duality" between invariant polynomials and closures of
group orbits. Namely, the orbit closure of a vector is...
Expander graphs are sparse and yet well-connected graphs.
Several applications in theoretical computer science require
explicit constructions of expander graphs, sometimes even with
additional structure. One approach to their construction is
to...
A binary code is simply any subset of 0/1 strings of a fixed
length. Given two strings, a standard way of defining their
distance is by counting the number of positions in which they
disagree. Roughly speaking, if elements of a code are
sufficiently...
The ABNNR encoding is a classical encoding scheme that amplifies
the distance of an error correcting code. The encoding takes an
error correcting code with a small distance and constructs an error
correcting code with distance approaching one, by...
