We give the first almost-linear time algorithm for computing
exact maximum flows and minimum-cost flows on directed graphs. By
well known reductions, this implies almost-linear time algorithms
for several problems including bipartite matching...
In interactive coding, Alice and Bob wish to compute some
function f of their private inputs x and y. They do this by
engaging in a non-adaptive (fixed speaking order, fixed length)
protocol to jointly compute f(x,y). The goal is to do this in
an...
The lifeblood of interactive proof systems is randomness,
without which interaction becomes redundant. Thus, a natural
long-standing question is which types of proof systems can indeed
be derandomized and collapsed to a single-message NP-type...
Algorithms for understanding data generated from distributions
over large discrete domains are of fundamental importance. In
this talk, we consider the sample complexity of *property testing
algorithms* that seek to to distinguish whether or not an...
Expander graphs are fundamental objects in theoretical computer
science and mathematics. They have numerous applications in diverse
fields such as algorithm design, complexity theory, coding theory,
pseudorandomness, group theory, etc.
The notion of Schmidt rank/strength for a collection of m
polynomials plays an important role in additive combinatorics,
number theory and commutative algebra; high rank collections of
polynomials are “psuedorandom”. An arbitrary collection
of...
central topic in the theory of computation
is derandomization: say we have an algorithm
which flips coins to achieve some goal, and succeeds with high
probability. Can we transform this algorithm into a deterministic
procedure, while maintaining...
It may seem quite obvious that graphs carry a lot of geometric
structure. Don't we learn in algorithm classes how to solve
all-pairs-shortest-paths, minimum spanning trees etc.?
However, in this talk, I will try to impress on you the idea
that...
One of the central problems of coding theory is to determine the
trade-off between the amount of information a code can carry
(captured by its rate) and its robustness to resist message
corruption (captured by its distance). One of the main
methods...
Thresholds for increasing properties of random structures are a
central concern in probabilistic combinatorics and related
areas. In 2006, Kahn and Kalai conjectured that for any
nontrivial increasing property on a finite set, its threshold
is...
