Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EXPANDER GRAPHS:
Reports tagged with Expander Graphs:
TR97-020 | 15th May 1997
Oded Goldreich

A Sample of Samplers -- A Computational Perspective on Sampling (survey).

We consider the problem of estimating the average of a huge set of values.
That is,
given oracle access to an arbitrary function $f:\{0,1\}^n\mapsto[0,1]$,
we need to estimate $2^{-n} \sum_{x\in\{0,1\}^n} f(x)$
upto an additive error of $\epsilon$.
We are allowed to employ a randomized algorithm which may ... more >>>

TR98-072 | 14th December 1998
Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

Deterministic Amplification of Space Bounded Probabilistic Algorithms.

This paper initiates the study of deterministic amplification of space
bounded probabilistic algorithms. The straightforward implementations of
known amplification methods cannot be used for such algorithms, since they
consume too much space. We present a new implementation of the
Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ... more >>>

TR99-046 | 17th November 1999
Ran Raz, Omer Reingold, Salil Vadhan

Extracting All the Randomness and Reducing the Error in Trevisan's Extractors

We give explicit constructions of extractors which work for a source of
any min-entropy on strings of length n. These extractors can extract any
constant fraction of the min-entropy using O(log^2 n) additional random
bits, and can extract all the min-entropy using O(log^3 n) additional
random bits. Both of these ... more >>>

TR00-090 | 3rd December 2000
Oded Goldreich

Candidate One-Way Functions Based on Expander Graphs

We suggest a candidate one-way function using combinatorial
constructs such as expander graphs. These graphs are used to
determine a sequence of small overlapping subsets of input bits,
to which a hard-wired random predicate is applied.
Thus, the function is extremely easy to evaluate:
all that is needed ... more >>>

TR01-018 | 23rd February 2001
Omer Reingold, Salil Vadhan, Avi Wigderson

Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors

The main contribution of this work is a new type of graph product, which we call the zig-zag
product. Taking a product of a large graph with a small graph, the resulting graph inherits
(roughly) its size from the large one, its degree from the small one, and ... more >>>

TR05-012 | 17th January 2005
Luca Trevisan, Salil Vadhan, David Zuckerman

Compression of Samplable Sources

We study the compression of polynomially samplable sources. In particular, we give efficient prefix-free compression and decompression algorithms for three classes of such sources (whose support is a subset of {0,1}^n).

1. We show how to compress sources X samplable by logspace machines to expected length H(X)+O(1).

Our next ... more >>>

TR05-022 | 19th February 2005
Omer Reingold, Luca Trevisan, Salil Vadhan

Pseudorandom Walks in Biregular Graphs and the RL vs. L Problem

Motivated by Reingold's recent deterministic log-space algorithm for Undirected S-T Connectivity (ECCC TR 04-94), we revisit the general RL vs. L question, obtaining the following results.

1. We exhibit a new complete problem for RL: S-T Connectivity restricted to directed graphs for which the random walk is promised to have ... more >>>

TR05-061 | 15th June 2005
Ronen Gradwohl, Guy Kindler, Omer Reingold, Amnon Ta-Shma

On the Error Parameter of Dispersers

Optimal dispersers have better dependence on the error than
optimal extractors. In this paper we give explicit disperser
constructions that beat the best possible extractors in some
parameters. Our constructions are not strong, but we show that
having such explicit strong constructions implies a solution
to the Ramsey graph construction ... more >>>

TR05-092 | 23rd August 2005
Eyal Rozenman, Salil Vadhan

Derandomized Squaring of Graphs

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

TR05-098 | 4th September 2005
Oded Goldreich

Bravely, Moderately: A Common Theme in Four Recent Results

We highlight a common theme in four relatively recent works
that establish remarkable results by an iterative approach.
Starting from a trivial construct,
each of these works applies an ingeniously designed
sequence of iterations that yields the desired result,
which is highly non-trivial. Furthermore, in each iteration,
more >>>

TR06-058 | 25th April 2006
Alexander Healy

Randomness-Efficient Sampling within NC^1

Revisions: 1

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

TR09-057 | 23rd June 2009
Yonatan Bilu, Nathan Linial

Are stable instances easy?

We introduce the notion of a stable instance for a discrete
optimization problem, and argue that in many practical situations
only sufficiently stable instances are of interest. The question
then arises whether stable instances of NP--hard problems are
easier to solve. In particular, whether there exist algorithms
that solve correctly ... more >>>

TR09-105 | 27th October 2009
Vikraman Arvind, Srikanth Srinivasan

The Remote Point Problem, Small Bias Spaces, and Expanding Generator Sets

Using $\epsilon$-bias spaces over F_2 , we show that the Remote Point Problem (RPP), introduced by Alon et al [APY09], has an $NC^2$ algorithm (achieving the same parameters as [APY09]). We study a generalization of the Remote Point Problem to groups: we replace F_n by G^n for an arbitrary fixed ... more >>>

TR09-135 | 10th December 2009
Zeev Dvir, Avi Wigderson

Monotone expanders - constructions and applications

The main purpose of this work is to formally define monotone expanders and motivate their study with (known and new) connections to other graphs and to several computational and pseudorandomness problems. In particular we explain how monotone expanders of constant degree lead to:
(1) Constant degree dimension expanders in finite ... more >>>

TR16-152 | 27th September 2016
Oded Goldreich

Deconstructing 1-local expanders

Revisions: 1

Contemplating the recently announced 1-local expanders of Viola and Wigderson (ECCC, TR16-129, 2016), one may observe that weaker constructs are well know. For example, one may easily obtain a 4-regular $N$-vertex graph with spectral gap that is $\Omega(1/\log^2 N)$, and similarly a $O(1)$-regular $N$-vertex graph with spectral gap $1/\tildeO(\log N)$.
more >>>

TR17-179 | 20th November 2017
Alexander Knop

IPS-like Proof Systems Based on Binary Decision Diagrams

It is well-known that there is equivalence between ordered resolution and ordered binary decision diagrams (OBDD) [LNNW95]; i.e., for any unsatisfiable formula ?, the size of the smallest ordered resolution refutation of ? equal to the size of the smallest OBDD for the canonical search problem corresponding to ?. But ... more >>>

TR19-032 | 4th March 2019
Srikanth Srinivasan

Strongly Exponential Separation Between Monotone VP and Monotone VNP

Revisions: 1

We show that there is a sequence of explicit multilinear polynomials $P_n(x_1,\ldots,x_n)\in \mathbb{R}[x_1,\ldots,x_n]$ with non-negative coefficients that lies in monotone VNP such that any monotone algebraic circuit for $P_n$ must have size $\exp(\Omega(n)).$ This builds on (and strengthens) a result of Yehudayoff (2018) who showed a lower bound of $\exp(\tilde{\Omega}(\sqrt{n})).$

more >>>

TR20-149 | 29th September 2020
Oded Goldreich, Avi Wigderson

Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing

Revisions: 2

A graph $G$ is called {\em self-ordered}\/ (a.k.a asymmetric) if the identity permutation is its only automorphism.
Equivalently, there is a unique isomorphism from $G$ to any graph that is isomorphic to $G$.
We say that $G=(V,E)$ is {\em robustly self-ordered}\/ if the size of the symmetric difference ... more >>>

TR20-151 | 8th October 2020
Venkatesan Guruswami, Vinayak Kumar

Pseudobinomiality of the Sticky Random Walk

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

TR20-191 | 27th December 2020

Negations Provide Strongly Exponential Savings

We show that there is a family of monotone multilinear polynomials over $n$ variables in VP, such that any monotone arithmetic circuit for it would be of size $2^{\Omega(n)}$. Before our result, strongly exponential lower bounds on the size of monotone circuits were known only for computing explicit polynomials in ... more >>>

TR21-175 | 6th December 2021
Oded Goldreich

On the Locally Testable Code of Dinur et al. (2021)

Revisions: 1

This text provides a high-level description of the locally testable code constructed by Dinur, Evra, Livne, Lubotzky, and Mozes (ECCC, TR21-151).
In particular, the group theoretic aspects are abstracted as much as possible.

more >>>

TR22-004 | 3rd January 2022
Silas Richelson, Sourya Roy

Analyzing Ta-Shma’s Code via the Expander Mixing Lemma

Random walks in expander graphs and their various derandomizations (e.g., replacement/zigzag product) are invaluable tools from pseudorandomness. Recently, Ta-Shma used s-wide replacement walks in his breakthrough construction of a binary linear code almost matching the Gilbert-Varshamov bound (STOC 2017). Ta-Shma’s original analysis was entirely linear algebraic, and subsequent developments have ... more >>>

ISSN 1433-8092 | Imprint