Omer Reingold

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

Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand

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

Mladen Mikša, Jakob Nordström

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

Benny Applebaum, Eliran Kachlon

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

Yotam Dikstein, Irit Dinur

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

Gil Cohen, Noam Peri, Amnon Ta-Shma

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