Dimitris Fotakis, Paul Spirakis

In this work we use random walks on expanders in order to

relax the properties of hitting sets required for partially

derandomizing one-side error algorithms. Building on a well-known

probability amplification technique [AKS87,CW89,IZ89], we use

random walks on expander graphs of subexponential (in the

random bit complexity) size so as ...
more >>>

Scott Aaronson

A celebrated 1976 theorem of Aumann asserts that honest, rational

Bayesian agents with common priors will never "agree to disagree": if

their opinions about any topic are common knowledge, then those

opinions must be equal. Economists have written numerous papers

examining the assumptions behind this theorem. But two key questions

more >>>

Luca Trevisan

Khot formulated in 2002 the "Unique Games Conjectures" stating that, for any epsilon > 0, given a system of constraints of a certain form, and the promise that there is an assignment that satisfies a 1-epsilon fraction of constraints, it is intractable to find a solution that satisfies even an ... more >>>

Eyal Rozenman, Salil Vadhan

We introduce a "derandomized" analogue of graph squaring. This

operation increases the connectivity of the graph (as measured by the

second eigenvalue) almost as well as squaring the graph does, yet only

increases the degree of the graph by a constant factor, instead of

squaring the degree.

One application of ... more >>>

Alexander Healy

We construct a randomness-efficient averaging sampler that is computable by uniform constant-depth circuits with parity gates (i.e., in AC^0[mod 2]). Our sampler matches the parameters achieved by random walks on constant-degree expander graphs, allowing us to apply a variety expander-based techniques within NC^1. For example, we obtain the following results:

... more >>>Frank Neumann, Carsten Witt

Ant Colony Optimization (ACO) is a kind of randomized search heuristic that has become very popular for solving problems from combinatorial optimization. Solutions for a given problem are constructed by a random walk on a so-called construction graph. This random walk can be influenced by heuristic information about the problem. ... more >>>

Satyen Kale, C. Seshadhri

We consider the problem of testing graph expansion in the bounded degree model. We give a property tester that given a graph with degree bound $d$, an expansion bound $\alpha$, and a parameter $\epsilon > 0$, accepts the graph with high probability if its expansion is more than $\alpha$, and ... more >>>

Greg Kuperberg, Shachar Lovett, Ron Peled

We show the existence of rigid combinatorial objects which previously were not known to exist. Specifically, for a wide range of the underlying parameters, we show the existence of non-trivial orthogonal arrays, $t$-designs, and $t$-wise permutations. In all cases, the sizes of the objects are optimal up to polynomial overhead. ... more >>>

Shachar Lovett, Sankeerth Rao Karingula, Alex Vardy

A new probabilistic technique for establishing the existence of certain regular combinatorial structures has been introduced by Kuperberg, Lovett, and Peled (STOC 2012). Using this technique, it can be shown that under certain conditions, a randomly chosen structure has the required properties of a $t-(n,k,?)$ combinatorial design with tiny, yet ... more >>>

Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, Shachar Lovett

We propose a new framework for constructing pseudorandom generators for $n$-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in $[-1,1]^n$. Next, we use a fractional pseudorandom generator as steps of a random walk in $[-1,1]^n$ that ... more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$).

We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon n$ edges from $G$ to make it $H$-minor free (for some small constant $\varepsilon > 0$). We give an $n^{1/2+o(1)}$-time randomized procedure that, with high probability, finds an ...
more >>>

Akash Kumar, C. Seshadhri, Andrew Stolman

Let $G$ be a graph with $n$ vertices and maximum degree $d$. Fix some minor-closed property $\mathcal{P}$ (such as planarity).

We say that $G$ is $\varepsilon$-far from $\mathcal{P}$ if one has to remove $\varepsilon dn$ edges to make it have $\mathcal{P}$.

The problem of property testing $\mathcal{P}$ was introduced in ...
more >>>

Alessandro Chiesa, Tom Gur, Igor Shinkar

Locally correctable codes (LCCs) are error correcting codes C : \Sigma^k \to \Sigma^n which admit local algorithms that correct any individual symbol of a corrupted codeword via a minuscule number of queries. This notion is stronger than that of locally decodable codes (LDCs), where the goal is to only recover ... more >>>

Venkatesan Guruswami, Vinayak Kumar

Random walks on expanders are a central and versatile tool in pseudorandomness. If an arbitrary half of the vertices of an expander graph are marked, known Chernoff bounds for expander walks imply that the number $M$ of marked vertices visited in a long $n$-step random walk strongly concentrates around the ... more >>>

Silas Richelson, Sourya Roy

In a breakthrough result, Ta-Shma described an explicit construction of an almost optimal binary code (STOC 2017). Ta-Shma's code has distance $\frac{1-\varepsilon}{2}$ and rate $\Omega\bigl(\varepsilon^{2+o(1)}\bigr)$ and thus it almost achieves the Gilbert-Varshamov bound, except for the $o(1)$ term in the exponent. The prior best list-decoding algorithm for (a variant of) ... more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>