Consider the following two-player communication process to decide a language L: The first player holds the entire input x but is polynomially bounded; the second player is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small ... more >>>

Impagliazzo, Paturi and Zane (JCSS 2001) proved a sparsification lemma for k-CNFs:
every k-CNF is a sub-exponential size disjunction of k-CNFs with a linear
number of clauses. This lemma has subsequently played a key role in the study
of the exact complexity of the satisfiability problem. A natural question is
more >>>

We give a deterministic, nearly logarithmic-space algorithm for mild spectral sparsification of undirected graphs. Given a weighted, undirected graph G on n vertices described by a binary string of length N, an integer k\leq \log n and an error parameter \varepsilon > 0, our algorithm runs in space $\tilde{O}(k\log (N\cdot ... more >>>