The Satisfiability problem is perhaps the most famous problem in
theoretical computer science, and significant effort has been
devoted to understanding randomly generated SAT instances. The
random k-SAT model (where a random k-CNF formula is chosen...
In the Pandora's Box problem, the algorithm is provided with a
number of boxes with unknown (stochastic) rewards contained inside
them. The algorithm can open any box at some cost, discover the
reward inside, and based on these observations can...
In a plethora of random models for constraint satisfaction and
statistical inference problems, researchers from different
communities have observed computational gaps between what
existential or brute-force methods promise, and what known
efficient...
In the max cut problem, we are given an n-vertex graph and we
are asked what is the maximum fraction of edges "cut" by any
partition of the vertices? This problem can be reformulated as an
optimization problem over the cut polytope, which has...
Some of the central questions in complexity theory address the
amortized complexity of computation (also sometimes known as direct
sum problems). While these questions appear in many contexts, they
are all variants of the following:
What edge density of a graph guarantees that that it will
contain a particular subgraph? Or one of a given
family F of subgraphs? The celebrated
Erdős--Stone--Simonovits Theorem characterizes the maximum edge
density in F-free graphs, in terms of...
Bernstein's theorem (also known as the
Bernstein-Khovanskii-Kushnirenko theorem) gives a bound on the
number of nonzero solutions of a polynomial system of equations in
terms of the mixed volume of its Newton polytopes. In this talk, we
will give...
Random sampling a subgraph of a graph is an important
algorithmic technique. Solving some problems on the (smaller)
subgraph is naturally faster, and can give either a useful
approximate answer, or sometimes even give a result that can be
quickly...
For a fixed integer k > 1, the Boolean k-XOR problem consists
of a system of linear equations mod 2 with each equation involving
exactly k variables. We give an algorithm to strongly refute
*semi-random* instances of the Boolean k-XOR problem on n...
This talk introduces a directed analog of the
classical Laplacian matrix and discusses algorithms for
solving certain problems related to them. Of particular interest is
that using such algorithms, one can compute the stationary
distribution of a...
