A principal challenge in realizing the potential of quantum
computing lies in our ability to perform computations
fault-tolerantly, in the presence of the noise inherent to quantum
devices. Non-Clifford quantum gates, which are analogous to
the...
Cayley graphs provide interesting bridges between graph theory,
additive combinatorics and group theory. Fixing an ambient finite
group, random Cayley graphs are constructed by choosing a
generating set at random. These graphs reflect interesting...
Finding regular subgraphs can be useful. Many results assume a
graph is regular or are easier to prove when they are. In 1975,
Erdős and Sauer asked for an estimate, for any constant r, on the
maximum number of edges an n-vertex graph can have...
Positive selector processes are natural stochastic processes
driven by sparse Bernoulli random variables. They play an important
role in the study of suprema of general stochastic processes, and
in particular, Talagrand posed the selector process...
Hindman’s Theorem states that whenever the natural numbers are
finitely coloured there exists an infinite sequence all of whose
finite sums are the same colour. By considering just powers of 2,
this immediately implies the corresponding result for...
Q1: A fundamental result in coding theory, known as the Plotkin
bound, suggests that a binary code can tolerate up to ¼ fraction of
adversarial corruptions. Can we design codes that handle more
errors if we allow interaction between the sender and...
We present a new method to solve algorithmic and combinatorial
problems by (1) reducing them to bounding the maximum, over x in
{-1, 1}^n, of homogeneous degree-q multilinear polynomials, and
then (2) bounding the maximum value attained by these...
The recent breakthrough of Limaye, Srinivasan and Tavenas (LST)
gave the first super-polynomial lower bounds against low-depth
algebraic circuits, for any field of zero (or sufficiently large)
characteristic. It was an open question to extend this...
In this talk, we present a new method to solve algorithmic and
combinatorial problems by (1) reducing them to bounding the
maximum, over x in {-1, 1}^n, of homogeneous degree-q multilinear
polynomials, and then (2) bounding the maximum value...
The satisfiability problem for Constraint Satisfaction Problems
(CSPs) asks whether an instance of a CSP has a fully satisfying
assignment, i.e., an assignment that satisfies all constraints.
This problem is known to be in class P or is NP-complete...
