Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Expander Graph:
TR04-094 | 10th November 2004
Omer Reingold

Undirected ST-Connectivity in Log-Space

We present a deterministic, log-space algorithm that solves
st-connectivity in undirected graphs. The previous bound on the
space complexity of undirected st-connectivity was
log^{4/3}() obtained by Armoni, Ta-Shma, Wigderson and
Zhou. As undirected st-connectivity is
complete for the class of problems solvable by symmetric,
non-deterministic, log-space computations (the class SL), ... more >>>

TR13-007 | 8th January 2013
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

Short lists with short programs in short time

Revisions: 1

Given a machine $U$, a $c$-short program for $x$ is a string $p$ such that $U(p)=x$ and the length of $p$ is bounded by $c$ + (the length of a shortest program for $x$). We show that for any universal machine, it is possible to compute in polynomial time on ... more >>>

TR15-078 | 4th May 2015
Mladen Mikša, Jakob Nordström

A Generalized Method for Proving Polynomial Calculus Degree Lower Bounds

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good ... more >>>

TR19-011 | 27th January 2019
Benny Applebaum, Eliran Kachlon

Sampling Graphs without Forbidden Subgraphs and Almost-Explicit Unbalanced Expanders

Revisions: 2

We initiate the study of the following hypergraph sampling problem: Sample a $d$-uniform hypergraph over $n$ vertices and $m$ hyperedges from some pseudorandom distribution $\mathcal{G}$ conditioned on not having some small predefined $t$-size hypergraph $H$ as a subgraph. The algorithm should run in $\mathrm{poly}(n)$-time even when the size of the ... more >>>

TR19-112 | 1st September 2019
Yotam Dikstein, Irit Dinur

Agreement testing theorems on layered set systems

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test.

Previous work has shown that high dimensional expansion ... more >>>

TR20-163 | 5th November 2020
Gil Cohen, Noam Peri, Amnon Ta-Shma

Expander Random Walks: A Fourier-Analytic Approach

In this work we ask the following basic question: assume the vertices of an expander graph are labelled by $0,1$. What "test" functions $f : \{ 0,1\}^t \to \{0,1\}$ cannot distinguish $t$ independent samples from those obtained by a random walk? The expander hitting property due to Ajtai, Komlos and ... more >>>

ISSN 1433-8092 | Imprint