In this talk, I will give new proofs for the hardness
amplification of fficiently samplable predicates and of weakly
verifiable puzzles. More oncretely, in the first part of the talk,
I will give a new proof of Yao's XOR-Lemma as well as
related...
We prove a complexity dichotomy theorem for all non-negatively
weighted counting Constraint Satisfaction Problems (#CSP). This
caps a long series of important results on counting problems
including unweighted and weighted graph homomorphisms and...
Non-relativization of complexity issues can be interpreted as
giving evidence that these issues cannot be resolved by
“black-box” techniques. We show that the assumption $DistNP
\subseteq AvgP$ does not imply that $NP\subseteq BPP$ by...
We show a (3/2-\epsilon)-approximation algorithm for the
graphical traveling salesman problem where the goal is to find a
shortest tour in an unweighted graph G. This is a special case of
the metric traveling salesman problem when the underlying...
We prove completeness results for certain class of functions
which have implications for automatic proving of
universally-composable security theorems for ideal and real
functionalities composed of if-then-else programs with (uniform)
random number...
The complexity of simple stochastic games (SSGs) has been open
since they were defined by Condon in 1992. Such a game is played by
two players, Min and Max, on a graph consisting of max nodes, min
nodes, and average nodes. The goal of Max is to...
Recently there has been much interest in polynomial threshold
functions in the context of learning theory, structural results and
pseudorandomness. A crucial ingredient in these works is the
understanding of the distribution of low-degree...
Erdos conjectured that N points in the plane determine at least
c N (log N)^{-1/2} different distances. Building on work of
Elekes-Sharir, Nets Katz and I showed that the number of distances
is at least c N (log N)^{-1} . (Previous estimates had...
A ``tournament'' is a digraph obtained from a complete graph by
directing its edges, and ``colouring'' a tournament means
partitioning its vertex set into acyclic subsets (``acyclic'' means
the subdigraph induced on the subset has no directed cycles...
A (q,k,t)-design matrix is an m x n matrix whose pattern of
zeros/non-zeros satisfies the following design-like condition: each
row has at most q non-zeros, each column has at least k non-zeros
and the supports of every two columns intersect in at...
