Computer Science and Discrete Mathematics (CSDM)

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...

In a sequence of recent papers, Sudan and coauthors have investigated the relation between testability of properties of Boolean functions and the invariance of the properties with respect to transformations of the domain. Linear-invariance is...

A hardness escalation method applies a simple transformation that increases the complexity of a computational problem. Using multiparty communication complexity we present a generic hardness escalation method that converts any family of...

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries:

1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword...

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial...