Computer Science and Discrete Mathematics (CSDM)

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

A "proof assistant" is a software package comprising a validity checker for proofs in a particular logic, accompanied by semi-decision procedures called "tactics" that assist the mathematician in filling in the easy parts of the proofs. I will...

The classical Dvoretzky theorem asserts that for every integer k>1 and every target distortion D>1 there exists an integer n=n(k,D) such that any
n-dimensional normed space contains a subspace of dimension k that embeds into Hilbert space with...

Infinite continuous graphs emerge naturally in the geometric analysis of closed planar sets which cannot be presented as countable union of convex sets. The classification of such graphs leads in turn to properties of large classes of real functions...

A perfect matching in a k-uniform hypergraph H = (V, E) on n vertices
is a set of n/k disjoint edges of H, while a fractional perfect matching
in H is a function w : E → [0, 1] such that for each v ∈ V we have
e∋v w(e) = 1. Given n ≥ 3 and 3 ≤ k ≤ n...

A permutation pi=(pi_{1},...,pi_{n}) is consecutive 123-avoiding if there is no sequence of the form pi_i pi_{i+1} pi_{i+2}. More generally, for S a collection of permutations on m+1 elements, this definition extends to define consecutive S...

The famous theorem of Szemerédi says that for any natural number $k$ and any $a > 0$ there exists n such that if $N >= n$ then any subset $A$ of the set $[N] ={1,2,...,N}$ of size $|A| >= a$ $N$ contains an arithmetic progression of length $k$. We...