We develop catalytic algorithms for fundamental problems in algorithm design that run in polynomial time, use only 𝒪(log(n)) workspace, and use sublinear catalytic space matching the best-known space bounds of non-catalytic algorithms running in polynomial time. First, we design a polynomial time algorithm for directed s-t connectivity using n / 2^{Θ(√{log n})} catalytic space, which matches the state-of-the-art time-space bounds in the non-catalytic setting [Barnes et al., 1998], and improves the catalytic space usage of the best known algorithm [James Cook and Edward Pyne, 2026]. Furthermore, using only 𝒪(log(n)) random bits we get a randomized algorithm whose running time nearly matches the fastest time bounds known for space-unrestricted algorithms. Second, we design polynomial time algorithms for the problems of computing Edit Distance, Longest Common Subsequence, and the Discrete Fréchet Distance, again using n / 2^{Θ(√{log n})} catalytic space. This again matches non-catalytic time-space frontier for Edit Distance and Least Common Subsequence [Kiyomi et al., 2021].

Consider a data structure problem with possible data coming from a set D, queries coming from a set Q, and in the dynamic case updates coming from a set U. Then, the current state of the art in data structure lower bounds is t = Ω(log|Q|) for static data structure problems, and max(tq,tu) = Ω((logn)2) where n = max(|Q|,|U|,log|D|) for dynamic. We port Razborov and Rudich’s natural-proofs framework to the setting of static and dynamic data structures in the cell probe model, in a way that strongly suggests this state of the art is unlikely to be improved anytime soon. A similar direction was recently taken also by Korten, Pitassi and Impagliazzo (FOCS 2025) who look at static data structure lower bounds in a different regime of parameters. Our contribution is: We define notions analogous to pseudo-random functions (PRF). We call these primitives local PRFs, in the context of static data structures, and local and locally updatable (LLU) PRFs, in the context of dynamic data structures. We then formulate cryptographic conjectures, namely, that secure local PRFs and secure LLU PRFs exist, precisely at the frontier where we are no longer able to prove static, respectively dynamic, data structure lower bounds. If these conjectures are true, it follows that the current state of the art in data structure lower bounds cannot be improved by a natural proof. We show that (almost) every single known data structure lower bound proof is a natural proof, by surveying all lower bounds in the literature known to us. (The only exception is proofs based on lifting theorems.) It follows that, if our cryptographic conjecture is true, then all known lower bound proof techniques (minus the one exception) are unable to improve upon the state of the art. (We also attempt to address the exception.) Further, we provide concrete candidate constructions for our two pseudo-random primitives. We conjecture that our constructions are secure for parameters just above the state-of-the-art lower bounds. We also show that, whether or not they are secure, our candidate PRFs at least satisfy the natural properties appearing in all (but one) known proofs. So if one is interested in improving upon the state of the art in static or dynamic data structure lower bounds, one must either find a non-natural method of proving such lower bounds (no such method currently exists), or one may as well begin by trying to break our PRF candidates.

A catalytic machine is a space-bounded Turing machine with additional access to a second, much larger work tape, with the caveat that this tape is full, and its contents must be preserved by the computation. Catalytic machines were defined by Buhrman et al. (STOC 2014), who, alongside many follow-up works, exhibited the power of catalytic space (CSPACE) and, in particular, catalytic logspace machines (CL) beyond that of traditional space-bounded machines. Several variants of CL have been proposed, including nondeterministic and co-non-deterministic catalytic computation by Buhrman et al. (STACS 2016) and randomized catalytic computation by Datta et al. (CSR 2020). These and other works proposed several questions, such as catalytic analogues of the theorems of Savitch and Immerman and Szelepcsényi. Catalytic computation was recently derandomized by Cook et al. (STOC 2025), but only in certain parameter regimes. We settle almost all questions regarding randomized and nondeterministic catalytic computation by giving an optimal reduction from catalytic space with additional resources to the corresponding non-catalytic space classes. With regards to non-determinism, our main result is that CL = CNL and with regards to randomness we show CL = CPrL where CPrL denotes randomized catalytic logspace where the accepting probability can be arbitrarily close to 1/2. We also have a number of near-optimal partial results for non-deterministic and randomized catalytic computation with less catalytic space. We show catalytic versions of Savitch’s theorem, Immerman-Szelepscényi, and the derandomization results of Nisan and Saks and Zhou, all of which are unconditional and hold for all parameter settings. Our results build on the compress-or-compute framework of Cook et al. (STOC 2025). Despite proving broader and stronger results, our framework is simpler and more modular.

The list-labeling problem captures the basic task of storing a dynamically changing set of up to$n$elements in sorted order in an array of size$m=(1+\Theta(1))n$• The goal is to support insertions and deletions while moving around elements within the array as little as possible. Until recently, the best known upper bound stood at$O(\log^{2}n)$amortized cost. This bound, which was first established in 1981, was finally improved two years ago, when a randomized$O(\log^{3/2}n)$expected-cost algorithm was discovered. The best randomized lower bound for this problem remains$\Omega(\log n)$, and closing this gap is considered to be a major open problem in data structures. In this paper, we present the See-Saw Algorithm, a randomized list-labeling solution that achieves a nearly optimal bound of$O(\log n \text{polyloglog}\ n)$amortized expected cost. This bound is achieved despite at least three lower bounds showing that this type of result is impossible for large classes of solutions.

Several measures exist for string similarity, including notable ones like the edit distance and the indel distance. The former measures the count of insertions, deletions, and substitutions required to transform one string into another, while the latter specifically quantifies the number of insertions and deletions. Many algorithmic solutions explicitly address one of these measures, and frequently techniques applicable to one can also be adapted to work with the other. In this paper, we investigate whether there exists a standardized approach for applying results from one setting to another. Specifically, we demonstrate the capability to reduce questions regarding string similarity over arbitrary alphabets to equivalent questions over a binary alphabet. Furthermore, we illustrate how to transform questions concerning indel distance into equivalent questions based on edit distance. This complements an earlier result of Tiskin (2007) which addresses the inverse direction.

We design an almost linear-size sketching scheme for computing edit distance up to a given threshold k. The scheme consists of two algorithms, a sketching algorithm and a recovery algorithm. The sketching algorithm depends on the parameter k and takes as input a string x and a public random string ρ and computes a sketch skρ(x;k), which is a compressed version of x. The recovery algorithm is given two sketches skρ(x;k) and skρ(y;k) as well as the public random string ρ used to create the two sketches, and (with high probability) if the edit distance ED(x,y) between x and y is at most k, will output ED(x,y) together with an optimal sequence of edit operations that transforms x to y, and if ED(x,y) > k will output large. The size of the sketch output by the sketching algorithm on input x is k2O(√log(n)loglog(n)) (where n is an upper bound on length of x). The sketching and recovery algorithms both run in time polynomial in n. The dependence of sketch size on k is information theoretically optimal and improves over the quadratic dependence on k in schemes of Kociumaka, Porat and Starikovskaya (FOCS’2021), and Bhattacharya and Koucký (STOC’2023).

In this paper we give an algorithm for streaming $k$-edit approximate pattern matching which uses space $\widetilde{O}(k^2)$ and time $\widetilde{O}(k^2)$ per arriving symbol. This improves substantially on the recent algorithm of Kociumaka, Porat and Starikovskaya (2022) which uses space $\widetilde{O}(k^5)$ and time $\widetilde{O}(k^8)$ per arriving symbol. In the $k$-edit approximate pattern matching problem we get a pattern $P$ and text $T$ and we want to identify all substrings of the text $T$ that are at edit distance at most $k$ from $P$. In the streaming version of this problem both the pattern and the text arrive in a streaming fashion symbol by symbol and after each symbol of the text we need to report whether there is a current suffix of the text with edit distance at most $k$ from $P$. We measure the total space needed by the algorithm and time needed per arriving symbol.

We consider the problem of obtaining approximation algorithms for standard edit distance and Dyck edit distance that are simple, deterministic and fast, but whose approximation factor may be high. For the standard edit distance of two strings, we introduce a class of simple and fast algorithms called basic single pass algorithms. Saha (2014) gave a randomized algorithm in this class that achieves an O(d) approximation on inputs x,y whose edit distance is O(d). In this paper, we (1) present a deterministic algorithm in this class that achieves similar performance and (2) prove that no algorithm (even randomized) in this class can give a better approximation factor. For the Dyck edit distance problem, Saha gave a randomized reduction from Dyck edit distance to standard two string edit distance at a cost of a O(log d) factor where d is the Dyck edit distance. We give a deterministic reduction whose description and proof are very simple.

In this paper we provide a new locally consistent decomposition of strings. Each string x is decomposed into blocks that can be described by grammars of size O(k) (using some amount of randomness). If we take two strings x and y of edit distance at most k then their block decomposition uses the same number of grammars and the i-th grammar of x is the same as the i-th grammar of y except for at most k indexes i. The edit distance of x and y equals to the sum of edit distances of pairs of blocks where x and y differ. Our decomposition can be used to design a sketch of size O(k2) for edit distance, and also a rolling sketch for edit distance of size O(k2). The rolling sketch allows to update the sketched string by appending a symbol or removing a symbol from the beginning of the string.

The edit distance (or Levenshtein distance) between two strings x, y is the minimum number of character insertions, deletions, and substitutions needed to convert x into y. It has numerous applications in various fields from text processing to bioinformatics so algorithms for edit distance computation attract lot of attention. In this talk I will survey recent progress on computational aspects of edit distance in several contexts: computing edit distance approximately, sketching and computing it in streaming model, exchanging strings in communication complexity model, and building error correcting codes for edit distance. I will point out many problems that are still open in those areas.

In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li and several data structure like problems such as non-adaptive function inversion of Hellman and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.

We build boolean circuits of size $O(nm^2)$ and depth $O(\log(n) + m \log(m))$ for sorting $n$ integers each of $m$-bits. We build also circuits that sort $n$ integers each of $m$-bits according to their first $k$ bits that are of size $O(nmk(1 + \log^*(n) - \log^*(m)))$ and depth $O(\log^{3}(n))$. This improves on the result of Asharov et al. arXiv:2010.09884 and resolves some of their open questions.

In this paper we study the computational complexity of functions that have efficient card-based protocols. Card-based protocols were proposed by den Boer [EUROCRYPT '89] as a means for secure two-party computation. Our contribution is two-fold: We classify a large class of protocols with respect to the computational complexity of functions they compute, and we propose other encodings of inputs which require fewer cards than the usual 2-card representation.

We show that for every $r \ge 2$ there exists $\epsilon_r > 0$ such that any $r$-uniform hypergraph with $m$ edges and maximum vertex degree $o(\sqrt{m})$ contains a set of at most $(\frac{1}{2} - \epsilon_r)m$ edges the removal of which breaks the hypergraph into connected components with at most $m/2$ edges. We use this to give an algorithm running in time $d^{(1 - \epsilon_r)m}$ that decides satisfiability of $m$-variable $(d, k)$-CSPs in which every variable appears in at most $r$ constraints, where $\epsilon_r$ depends only on $r$ and $k\in o(\sqrt{m})$. Furthermore our algorithm solves the corresponding #CSP-SAT and Max-CSP-SAT of these CSPs. We also show that CNF representations of unsatisfiable $(2, k)$-CSPs with variable frequency $r$ can be refuted in tree-like resolution in size $2^{(1 - \epsilon_r)m}$. Furthermore for Tseitin formulas on graphs with degree at most $k$ (which are $(2, k)$-CSPs) we give a deterministic algorithm finding such a refutation.

Given a Boolean function $f:\{-1,1\}^n\to \{-1,1\}$, the Fourier distribution assigns probability $\widehat{f}(S)^2$ to $S\subseteq [n]$. The Fourier Entropy-Influence (FEI) conjecture of Friedgut and Kalai asks if there exist a universal constant C>0 such that $H(\hat{f}^2)\leq C Inf(f)$, where $H(\hat{f}^2)$ is the Shannon entropy of the Fourier distribution of $f$ and $Inf(f)$ is the total influence of $f$. 1) We consider the weaker Fourier Min-entropy-Influence (FMEI) conjecture. This asks if $H_{\infty}(\hat{f}^2)\leq C Inf(f)$, where $H_{\infty}(\hat{f}^2)$ is the min-entropy of the Fourier distribution. We show $H_{\infty}(\hat{f}^2)\leq 2C_{\min}^\oplus(f)$, where $C_{\min}^\oplus(f)$ is the minimum parity certificate complexity of $f$. We also show that for every $ε\geq 0$, we have $H_{\infty}(\hat{f}^2)\leq 2\log (\|\hat{f}\|_{1,ε}/(1-ε))$, where $\|\hat{f}\|_{1,ε}$ is the approximate spectral norm of $f$. As a corollary, we verify the FMEI conjecture for the class of read-$k$ $DNF$s (for constant $k$). 2) We show that $H(\hat{f}^2)\leq 2 aUC^\oplus(f)$, where $aUC^\oplus(f)$ is the average unambiguous parity certificate complexity of $f$. This improves upon Chakraborty et al. An important consequence of the FEI conjecture is the long-standing Mansour's conjecture. We show that a weaker version of FEI already implies Mansour's conjecture: is $H(\hat{f}^2)\leq C \min\{C^0(f),C^1(f)\}$?, where $C^0(f), C^1(f)$ are the 0- and 1-certificate complexities of $f$, respectively. 3) We study what FEI implies about the structure of polynomials that 1/3-approximate a Boolean function. We pose a conjecture (which is implied by FEI): no "flat" degree-$d$ polynomial of sparsity $2^{ω(d)}$ can 1/3-approximate a Boolean function. We prove this conjecture unconditionally for a particular class of polynomials.

For any T ≥ 1, there are constants R=R(T) ≥ 1 and ζ=ζ(T)>0 and a randomized algorithm that takes as input an integer n and two strings x,y of length at most n, and runs in time O(n 1+1/T ) and outputs an upper bound U on the edit distance of edit(x,y) that with high probability, satisfies U ≤ R(edit(x,y)+n 1−ζ). In particular, on any input with edit(x,y) ≥ n 1−ζ the algorithm outputs a constant factor approximation with high probability. A similar result has been proven independently by Brakensiek and Rubinstein (this proceedings).

We give a combinatorial analysis (using edge expansion) of a variant of the iterative expander construction due to Reingold, Vadhan, and Wigderson [44], and show that this analysis can be formalized in the bounded arithmetic system VNC1 (corresponding to the “NC1 reasoning”). As a corollary, we prove the assumption made by Jeřábek [28] that a construction of certain bipartite expander graphs can be formalized in VNC1. This in turn implies that every proof in Gentzen's sequent calculus LK of a monotone sequent can be simulated in the monotone version of LK (MLK) with only polynomial blowup in proof size, strengthening the quasipolynomial simulation result of Atserias, Galesi, and Pudlák [9].

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer, and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n ). In this article, we provide an algorithm with running time Õ( n 2−2/7 ) that approximates the edit distance within a constant factor.

We consider the approximate pattern matching problem under edit distance. In this problem we are given a pattern P of length m and a text T of length n over some alphabet Σ, and a positive integer k. The goal is to find all the positions j in T such that there is a substring of T ending at j which has edit distance at most k from the pattern P. Recall, the edit distance between two strings is the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. For a position t in {1,...,n}, let kt be the smallest edit distance between P and any substring of T ending at t. In this paper we give a constant factor approximation to the sequence k1,k2,...,kn. We consider both offline and online settings. In the offline setting, where both P and T are available, we present an algorithm that for all t in {1,...,n}, computes the value of kt approximately within a constant factor. The worst case running time of our algorithm is Õ(nm3/4). In the online setting, we are given P and then T arrives one symbol at a time. We design an algorithm that upon arrival of the t-th symbol of T computes kt approximately within O(1)multiplicative factor and m8/9-additive error. Our algorithm takes Õ(m1−(7/54)) amortized time per symbol arrival and takes Õ(m1−(1/54)) additional space apart from storing the pattern P. Both of our algorithms are randomized and produce correct answer with high probability. To the best of our knowledge this is the first algorithm that takes worst-case sublinear (in the length of the pattern) time and sublinear extra space for the online approximate pattern matching problem. To get our result we build on the technique of Chakraborty, Das, Goldenberg, Koucký and Saks [FOCS'18] for computing a constant factor approximation of edit distance in sub-quadratic time.

We generalize the deterministic simulation theorem of Raz & McKenzie (Combinatorica 19(3):403–435, 1999 ), to any gadget which satisfies a certain hitting property. We prove that inner product and gap-Hamming satisfy this property, and as a corollary, we obtain a deterministic simulation theorem for these gadgets, where the gadget’s input size is logarithmic in the input size of the outer function. This yields the first deterministic simulation theorem with a logarithmic gadget size, answering an open question posed by Göös, Pitassi & Watson (in: Proceedings of the 56th FOCS, 2015 ). Our result also implies the previous results for the indexing gadget, with better parameters than was previously known. Moreover, a simulation theorem with logarithmic-sized gadget implies a quadratic separation in the deterministic communication complexity and the logarithm of the 1-partition number, no matter how high the 1-partition number is with respect to the input size—something which is not achievable by previous results of Göös, Pitassi & Watson ( 2015 ).

In the online labeling problem with parameters $n$ and $m$ we are presented with a sequence of $n$ items from a totally ordered universe $U$ and must assign each arriving item a label from the label set $\left\{1,\ldots,m\right\}$ so that the order of labels respects the order on $U$. As new items arrive it may be necessary to change the labels of some items; such changes may be done at any time at unit cost for each change. The goal is to minimize the total cost. An alternative formulation of this problem is the file maintenance problem, in which the items are maintained in sorted order in an array of length $m$, and we pay unit cost for moving an item. For the case $m=cn$ for constant $c>1$, an algorithm of Itai, Konheim, and Rodeh (1981) achieves total cost $O(n (\log n)^2)$, which is asymptotically optimal (Bulánek, Koucký, and Saks (2015)). For the case of $m=\Theta(n^{1+C})$ for constant $C>0$, algorithms are known that use $O(n \log n)$ relabelings. A matching lower bound was provided in Dietz, Seiferas, and Zhang (2005). The lower bound proof had two parts: a lower bound for a problem called prefix bucketing and a reduction from prefix bucketing to online labeling. We present a simplified version of their reduction, together with a full proof (which was not given in Dietz, Seiferas, and Zhang (2004)). We also simplify and improve the analysis of the prefix bucketing lower bound. This improvement allows us to extend the lower bounds for online labeling to larger $m$. Our lower bound for $m$ from $n^{1+C}$ to $2^n$ is $\Omega((n \log n) / (\log \log m - \log\log n))$. This reduces to the asymptotically optimal bound $\Omega(n \log n)$ when $m = \Theta(n^{1+C})$. We show that our bound is asymptotically optimal for the case of $m \geq 2^{1+(\log n)^{3}}$ by giving a matching upper bound.

A quasi-Gray code of dimension n and length l over an alphabet Sigma is a sequence of distinct words w_1,w_2,...,w_l from Sigma^n such that any two consecutive words differ in at most c coordinates, for some fixed constant c>0. In this paper we are interested in the read and write complexity of quasi-Gray codes in the bit-probe model, where we measure the number of symbols read and written in order to transform any word w_i into its successor w_{i+1}. We present construction of quasi-Gray codes of dimension n and length 3^n over the ternary alphabet {0,1,2} with worst-case read complexity O(log n) and write complexity 2. This generalizes to arbitrary odd-size alphabets. For the binary alphabet, we present quasi-Gray codes of dimension n and length at least 2^n - 20n with worst-case read complexity 6+log n and write complexity 2. This complements a recent result by Raskin [Raskin '17] who shows that any quasi-Gray code over binary alphabet of length 2^n has read complexity Omega(n). Our results significantly improve on previously known constructions and for the odd-size alphabets we break the Omega(n) worst-case barrier for space-optimal (non-redundant) quasi-Gray codes with constant number of writes. We obtain our results via a novel application of algebraic tools together with the principles of catalytic computation [Buhrman et al. '14, Ben-Or and Cleve '92, Barrington '89, Coppersmith and Grossman '75].

Edit distance is a measure of similarity of two strings based on the minimum number of character insertions, deletions, and substitutions required to transform one string into the other. The edit distance can be computed exactly using a dynamic programming algorithm that runs in quadratic time. Andoni, Krauthgamer and Onak (2010) gave a nearly linear time algorithm that approximates edit distance within approximation factor poly(log n). In this paper, we provide an algorithm with running time Õ(n^2-2/7) that approximates the edit distance within a constant factor.

In this paper we propose models of combinatorial algorithms for the Boolean Matrix Multiplication (BMM), and prove lower bounds on computing BMM in these models. First, we give a relatively relaxed combinatorial model which is an extension of the model by Angluin (1976), and we prove that the time required by any algorithm for the BMM is at least $Ω(n^3 / 2^{O( \sqrt{ \log n })})$. Subsequently, we propose a more general model capable of simulating the "Four Russians Algorithm". We prove a lower bound of $Ω(n^{7/3} / 2^{O(\sqrt{ \log n })})$ for the BMM under this model. We use a special class of graphs, called $(r,t)$-graphs, originally discovered by Rusza and Szemeredi (1978), along with randomization, to construct matrices that are hard instances for our combinatorial models.

We develop a new technique for proving lower bounds in the setting of asymmetric communication, a model that was introduced in the famous works of Miltersen (STOC’94) and Miltersen, Nisan, Safra and Wigderson (STOC’95). At the core of our technique is the first simulation theorem in the asymmetric setting, where Alice gets a p × n matrix x over F2 and Bob gets a vector y ∈ F2n. Alice and Bob need to evaluate f(x· y) for a Boolean function f: {0,1}p → {0,1}. Our simulation theorems show that a deterministic/randomized communication protocol exists for this problem, with cost C· n for Alice and C for Bob, if and only if there exists a deterministic/randomized *parity decision tree* of cost Θ(C) for evaluating f.

We consider the problem of elimination in communication complexity, that was first raised by Ambainis et al. [1] and later studied by Beimel et al. [4] for its connection to the famous direct sum question. In this problem, let f: {0, 1}2n → {0,1} be any boolean function. Alice and Bob get k inputs x1,⋯, xk and y1,⋯, yk respectively, with xi, yi ∈ {0, 1}n. They want to output a k-bit vector v, such that there exists one index i for which vi = f(xi,yi). We prove a general result lower bounding the randomized communication complexity of the elimination problem for f using its discrepancy. Consequently, we obtain strong lower bounds for the functions Inner-Product and Greater-Than, that work for exponentially larger values of k than the best previous bounds. To prove our result, we use a pseudo-random notion called regularity that was first used by Raz and Wigderson [19]. We show that functions with small discrepancy are regular. We also observe that a weaker notion, that we call weak-regularity, already implies hardness of elimination. Finally, we give a different proof, borrowing ideas from Viola [23], to show that Greater-Than is weakly regular.

Catalytic computation, defined by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), is a space-bounded computation where in addition to our working memory we have an exponentially larger auxiliary memory which is full; the auxiliary memory may be used throughout the computation, but it must be restored to its initial content by the end of the computation. Motivated by the surprising power of this model, we set out to study the non-deterministic version of catalytic computation. We establish that non-deterministic catalytic log-space is contained in ZPP, which is the same bound known for its deterministic counterpart, and we prove that non-deterministic catalytic space is closed under complement (under a standard derandomization assumption). Furthermore, we establish hierarchy theorems for non-deterministic and deterministic catalytic computation.

The Hamming and the edit metrics are two common notions of measuring distances between pairs of strings x,y lying in the Boolean hypercube. The edit distance between x and y is defined as the minimum number of character insertion, deletion, and bit flips needed for converting x into y. Whereas, the Hamming distance between x and y is the number of bit flips needed for converting x to y. In this paper we study a randomized injective embedding of the edit distance into the Hamming distance with a small distortion. We show a randomized embedding with quadratic distortion. Namely, for any x,y satisfying that their edit distance equals k, the Hamming distance between the embedding of x and y is O(k2) with high probability. This improves over the distortion ratio of O( n * n) obtained by Jowhari (2012) for small values of k. Moreover, the embedding output size is linear in the input size and the embedding can be computed using a single pass over the input. We provide several applications for this embedding. Among our results we provide a one-pass (streaming) algorithm for edit distance running in space O(s) and computing edit distance exactly up-to distance s1/6. This algorithm is based on kernelization for edit distance that is of independent interest.

Newman’s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with but a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct-sum theorems through the compression of interactive communication in the bounded-round setting. To obtain this application, we prove a new one-shot variant of the Slepian–Wolf coding theorem, interesting in its own right. Furthermore, we show that if a Reverse Newman’s Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.

One of the major outstanding foundational problems about boolean functions is the sensitivity conjecture, which (in one of its many forms) asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A strong enough lower bound on the cost of this game would imply the sensitivity conjecture.

We consider the file maintenance problem (also called the online labeling problem) in which $n$ integer items from the set $\{1,\ldots,r\}$ are to be stored in an array of size $m \geq n$. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If $r \leq m$ then we can simply store item $j$ in location $j$ but if $r > m$ then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of moves the algorithm has to do. This problem is nontrivial for $n\le m < r$. In the case that $m = Cn$ for some $C>1$, algorithms are known that solve the problem with cost $O(n\log^2(n))$ (independent of $r$). For the case $m=n$, algorithms with cost $O(n\log^3(n))$ were given. In this paper we prove lower bounds that show that these algorithms are optimal, up to constant factors. Previously, a lower bound of $\Omega(n\log^2(n))$ was known for the restricted class of smooth algorithms [J. Zhang, Ph.D. thesis, University of Rochester, Rochester, NY].

We define the notion of a catalytic-space computation. This is a computation that has a small amount of clean space available and is equipped with additional auxiliary space, with the caveat that the additional space is initially in an arbitrary, possibly incompressible, state and must be returned to this state when the computation is finished. We show that the extra space can be used in a nontrivial way, to compute uniform TC1-circuits with just a logarithmic amount of clean space. The extra space thus works analogously to a catalyst in a chemical reaction. TC1-circuits can compute for example the determinant of a matrix, which is not known to be computable in logspace.

Newman's theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and convert it into one that only uses public randomness while preserving the information revealed to each player? We prove that the answer is yes, at least for protocols that use a bounded number of rounds. As an application, we prove new direct sum theorems through the compression of interactive communication in the bounded-round setting. Furthermore, we show that if a Reverse Newman's Theorem can be proven in full generality, then full compression of interactive communication and fully-general direct-sum theorems will result.

We bound the minimum number$w$of wires needed to compute any (asymptotically good) error-correcting code$C:\{0,1\}^{\Omega (n)}\to\{0,1\}^{n}$with minimum distance$\Omega (n)$, using unbounded fan-in circuits of depth$d$with arbitrary gates. Our main results are: 1) if$d=2$, then$w=\Theta (n ({\lg n/\lg\lg n})^{2})$; 2) if$d=3$, then$w=\Theta (n\lg\lg n)$; 3) if$d=2k$or$d=2k+1$for some integer$k\geq 2$, then$w=\Theta (n\lambda_{k}(n))$, where$\lambda_{1}(n)=\lceil\lg n\rceil$,$\lambda_{i+1}(n)=\lambda_{i}^{\ast}(n)$, and the$\ast$operation gives how many times one has to iterate the function$\lambda_{i}$to reach a value at most 1 from the argument$n$; and 4) if$d=\lg^{\ast}n$, then$w=O(n)$. For depth$d=2$, our$\Omega (n ({\lg n/\lg\lg n})^{2})$lower bound gives the largest known lower bound for computing any linear map. The upper bounds imply that a (necessarily dense) generator matrix for our code can be written as the product of two sparse matrices. Using known techniques, we also obtain similar (but not tight) bounds for computing pairwise-independent hash functions. Our lower bounds are based on a superconcentrator-like condition that the graphs of circuits computing good codes must satisfy. This condition is provably intermediate between superconcentrators and their weakenings considered before.

In 1989 Kushilevitz initiated the study of iinformation-theoretic privacy within the context of communication complexity. Unfortunately, it has been shown that most interesting functions are not privately computable. The unattainability of perfect privacy for many functions motivated the study of approximate privacy. Feigenbaum et al. define notions of worst-case as well as average-case approximate privacy, and present several interesting upper bounds, and some open problems for further study. In this paper, we obtain asymptotically tight bounds on the tradeoffs between both the worst-case and average-case approximate privacy of protocols and their communication cost for Vickrey-auctions. Further, we relate the notion of average-case approximate privacy to other measures based on information cost of protocols. This enables us to prove exponential lower bounds on the subjective approximate privacy of protocols for computing the Intersection function, independent of its communication cost. This proves a conjecture of Feigenbaum et al.

We consider the file maintenance problem (also called the online labeling problem) in which n integer items from the set {1,...,r} are to be stored in an array of size m ≥ n. The items are presented sequentially in an arbitrary order, and must be stored in the array in sorted order (but not necessarily in consecutive locations in the array). Each new item must be stored in the array before the next item is received. If r ≤ m then we can simply store item j in location j but if r>m then we may have to shift the location of stored items to make space for a newly arrived item. The algorithm is charged each time an item is stored in the array, or moved to a new location. The goal is to minimize the total number of such moves the algorithm has to do. This problem is non-trivial when n ≤ m < r.

We bound the minimum number w of wires needed to compute any (asymptotically good) error-correcting code C:{0,1}Ω(n) -> {0,1}n with minimum distance Ω(n), using unbounded fan-in circuits of depth d with arbitrary gates. Our main results are: (1) If d=2 then w = Θ(n ({log n/ log log n})2). (2) If d=3 then w = Θ(n lg lg n). (3) If d=2k or d=2k+1 for some integer k ≥ 2 then w = Θ(n λk(n)), where λ1(n)=⌈ log n⌉, λi+1(n)= λi*(n), and the * operation gives how many times one has to iterate the function λi to reach a value at most 1 from the argument n. (4) If d=log* n then w=O(n).

Shapley's discounted stochastic games, Everett's recursive games and Gillette's undiscounted stochastic games are classical models of game theory describing two-player zero-sum games of potentially infinite duration. We describe algorithms for exactly solving these games. When the number of positions of the game isbconstant, our algorithms run in polynomial time.

We prove that the pseudorandom generator introduced by Impagliazzo Nisan and Wigderson with proper choice of parameters fools group products of a given finite group. The seed length is logarithmic in the size of the inputs.

In this paper we show that BPP is truth-table reducible to the set of Kolmogorov random strings R_K. It was previously known that PSPACE, and hence BPP is Turing-reducible to R_K. The earlier proof relied on the adaptivity of the Turing-reduction to find a Kolmogorov-random string of polynomial length using the set R_K as oracle. Our new non-adaptive result relies on a new fundamental fact about the set R_K, namely each initial segment of the characteristic sequence of R_K has high Kolmogorov complexity. As a partial converse to our claim we show that strings of very high Kolmogorov-complexity when used as advice are not much more useful than randomly chosen strings.

We observe that many important computational problems in NC 1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC 0 circuits if and only if it has TC 0 circuits of size n 1+ϵ for every ϵ> 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC 1 and has the self-reducibility property. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC 0 circuits of size n 1+ϵ d . If one were able to improve this lower bound to show that there is some constant ϵ> 0 (independent of the depth d ) such that every TC 0 circuit family recognizing BFE has size at least n 1+ϵ , then it would follow that TC 0 ≠ NC 1 . We show that proving lower bounds of the form n 1+ϵ is not ruled out by the Natural Proof framework of Razborov and Rudich and hence there is currently no known barrier for separating classes such as ACC 0 , TC 0 and NC 1 via existing “natural” approaches to proving circuit lower bounds. We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC 0 and AC 0 [6] circuits of size n 1+ c for some constant c depending on d .

The class TFNP, defined by Megiddo and Papadimitriou, consists of multivalued functions with values that are polynomially verifiable and guaranteed to exist. Do we have evidence that such functions are hard, for example, if TFNP is computable in polynomial-time does this imply the polynomial-time hierarchy collapses? By computing a multivalued function in deterministic polynomial-time we mean on every input producing one of the possible values of the function on that input. We give a relativized negative answer to this question by exhibiting an oracle under which TFNP functions are easy to compute but the polynomial-time hierarchy is infinite. We also show that relative to this same oracle, P≠UP and TFNP NP functions are not computable in polynomial-time with an NP oracle.

Barrington, Straubing and Therien (1990) conjectured that the Boolean AND function can not be computed by polynomial size constant depth circuits built from modular counting gates, i.e., by CC^0 circuits. In this work we show that the AND function can be computed by uniform probabilistic CC^0 circuits that use only O(log n) random bits. This may be viewed as evidence contrary to the conjecture. As a consequence of our construction we get that all of ACC^0 can be computed by probabilistic CC^0 circuits that use only O(log n) random bits. Thus, if one were able to derandomize such circuits, we would obtain a collapse of circuit classes giving ACC^0=CC^0. We present a derandomization of probabilistic CC^0 circuits using AND and OR gates to obtain ACC^0 = AND o OR o CC^0 = OR o AND o CC^0. AND and OR gates of sublinear fan-in suffice. Both these results hold for uniform as well as non-uniform circuit classes. For non-uniform circuits we obtain the stronger conclusion that ACC^0 = rand-ACC^0 = rand-CC^0 = rand(log n)-CC^0, i.e., probabilistic ACC^0 circuits can be simulated by probabilistic CC^0 circuits using only O(log n) random bits. As an application of our results we obtain a characterization of ACC^0 by constant width planar nondeterministic branching programs, improving a previous characterization for the quasipolynomial size setting.

We exhibit a deterministic concurrent reachability game PURGATORY$_n$ with $n$ non-terminal positions and a binary choice for both players in every position so that any positional strategy for Player 1 achieving the value of the game within given $\epsilon

We observe that many important computational problems in NC^1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial size TC^0 circuits if and only if it has TC^0 circuits of size n^{1+\epsilon} for every \epsilon ≫ 0 (counting the number of wires in a circuit as the size of the circuit). As an example of what this observation yields, consider the Boolean Formula Evaluation problem (BFE), which is complete for NC^1. It follows from a lower bound of Impagliazzo, Paturi, and Saks, that BFE requires depth d TC^0 circuits of size n^{1+\epsilon_d}. If one were able to improve this lower bound to show that there is some constant \epsilon≫0 such that every TC^0 circuit family recognizing BFE has size n^{1+\epsilon}, then it would follow that TC^0 \not= \NC^1. We also show that problems with small uniform constant-depth circuits have algorithms that simultaneously have small space and time bounds. We then make use of known time-space tradeoff lower bounds to show that SAT requires uniform depth d TC^0 and AC^0[6] circuits of size n^{1+c} for some constant c depending on d.

In this paper we study the individual communication complexity of the following problem. Alice receives an input string x and Bob an input string y, and Alice has to output y. For deterministic protocols it has been shown in Buhrman et al. (2004), that C(y) many bits need to be exchanged even if the actual amount of information C(y|x) is much smaller than C(y). It turns out that for randomised protocols the situation is very different. We establish randomised protocols whose communication complexity is close to the information theoretical lower bound. We furthermore initiate and obtain results about the randomised round complexity of this problem and show trade-offs between the amount of communication and the number of rounds. In order to do this we establish a general framework for studying these types of questions.

We pose a new and intriguing question motivated by distributed computing regarding random walks on graphs: How long does it take for several independent random walks, starting from the same vertex, to cover an entire graph? We study the cover time - the expected time required to visit every node in a graph at least once - and we show that for a large collection of interesting graphs, running many random walks in parallel yields a speed-up in the cover time that is linear in the number of parallel walks. We demonstrate that an exponential speed-up is sometimes possible, but that some natural graphs allow only a logarithmic speed-up. A problem related to ours (in which the walks start from some probablistic distribution on vertices) was previously studied in the context of space efficient algorithms for undirected s-t-connectivity and our results yield, in certain cases, an improvement upon some of the earlier bounds.

In this paper we prove that the class of functions expressible by first order formulas with only two variables coincides with the class of functions computable by AC/sup 0/ circuits with a linear number of gates. We then investigate the feasibility of using Ehrenfeucht-Fraisse games to prove lower bounds for that class of circuits, as well as for general AC/sup 0/ circuits.

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and nonuniform reductions. These sets are provably not complete under the usual many-one reductions. Let ${{R_{\rm C}}}, {{R_{\rm Kt}}}, {{R_{\rm KS}}}, {{R_{\rm KT}}}$ be the sets of strings x having complexity at least $|x|/2$, according to the usual Kolmogorov complexity measure ${\mbox{\rm C}}$, Levin's time-bounded Kolmogorov complexity ${\mbox{\rm Kt}}$ [L. Levin, Inform. and Control, 61 (1984), pp. 15-37], a space-bounded Kolmogorov measure ${\mbox{\rm KS}}$, and a new time-bounded Kolmogorov complexity measure ${\mbox{\rm KT}}$, respectively. Our main results are as follows: \begin{remunerate} \item ${{R_{\rm KS}}}$ and ${{R_{\rm Kt}}}$ are complete for ${{\rm{PSPACE}}}$ and {\mbox{\rm EXP}}, respectively, under ${\mbox{\rm P/poly}}$-truth-table reductions. Similar results hold for other classes with ${{\rm{PSPACE}}}$-robust Turing complete sets. \item ${\mbox{\rm EXP}} = {\mbox{\rm NP}}^{{{R_{\rm Kt}}}}.$ \item ${{\rm{PSPACE}}} = {\mbox{\rm ZPP}}^{{{R_{\rm KS}}}} \subseteq {\mbox{\rm P}}^{{{R_{\rm C}}}}$. \item The Discrete Log, Factoring, and several lattice problems are solvable in ${\mbox{\rm BPP}}^{{{R_{\rm KT}}}}$. \end{remunerate} Our hardness result for ${{\rm{PSPACE}}}$ gives rise to fairly natural problems that are complete for ${{\rm{PSPACE}}}$ under ${\mbox{$\leq^{\rm p}_{\rm T}$}}$ reductions, but not under ${\mbox{$\leq^{\rm log}_{\rm m}$}}$ reductions. Our techniques also allow us to show that all computably enumerable sets are reducible to ${{R_{\rm C}}}$ via ${\mbox{\rm P/poly}}$-truth-table reductions. This provides the first "efficient" reduction of the halting problem to ${{R_{\rm C}}}$.

We develop a new method to analyze the flow of communication in constant-depth circuits. This point of view allows usto prove new lower bounds on the number of wires required to recognize certain languages. We are able to provide explicit languages that can be recognized by AC0 circuits with O(n) gates but not with O(n) wires, and similarly for ACC0 circuits. We are also able to characterize exactly the regular languages that can be recognized with O(n) wires, both in AC0 and ACC0 framework.

We continue an investigation of resource-bounded Kolmogorov complexity and derandomization techniques begun in [E. Allender (2001), E. Allender et al., (2002)]. We introduce nondeterministic time-bounded Kolmogorov complexity measures (KNt and KNT) and examine the properties of these measures using constructions of hitting set generators for nondeterministic circuits [P. B. Miltersen et al., (1999), R. Shaltiel et al., (2001)]. We observe that KNt bears many similarities to the nondeterministic distinguishing complexity CND of [H. Buhrman et al., (2002)]. This motivates the definition of a new notion of time-bounded distinguishing complexity KDt, as an intermediate notion with connections to the class FewEXP. The set of KDt-random strings is complete for EXP under P/poly reductions. Most of the notions of resource-bounded Kolmogorov complexity discussed here and in [E. Allender (2001), E. Allender et al., (2002)] have close connections to circuit size (on different types of circuits). We extend this framework to define notions of Kolmogorov complexity KB and KF that are related to branching program size and formula size, respectively. The sets of KB- and KF-random strings lie in coNP; we show that oracle access to these sets enables one to factor Blum integers. We obtain related intractability results for approximating minimum formula size, branching program size, and circuit size. The NEXP/spl sube/NC and NEXP/spl sube/L/poly questions are shown to be equivalent to conditions about the KF and KB complexity of sets in P.

We show that sets consisting of strings of high Kolmogorov complexity provide examples of sets that are complete for several complexity classes under probabilistic and non-uniform reductions. These sets are provably not complete under the usual many-one reductions. Let R/sub K/, R/sub Kt/, R/sub KS/, R/sub KT/ be the sets of strings x having complexity at least |x|/2, according to the usual Kolmogorov complexity measure K, Levin's time-bounded Kolmogorov complexity Kt [27], a space-bounded Kolmogorov measure KS, and the time-bounded Kolmogorov complexity measure KT that was introduced in [4], respectively. Our main results are: 1. R/sub KS/ and R/sub Kt/ are complete for PSPACE and EXP, respectively, under P/poly-truth-table reductions. 2. EXP = NP/sup R(Kt)/. 3. PSPACE = ZPP/sup R(KS)/ /spl sube/ P/sup R(K)/. 4. The Discrete Log, Factoring, and several lattice problems are solvable in BPP/sup R(KT)/.

Extends the lower-bound techniques of L. Fortnow (2000) to the unbounded-error probabilistic model. A key step in the argument is a generalization of V.A. Nepomnjas/spl caron/c/spl caron/ii/spl breve/'s (1970) theorem from the Boolean setting to the arithmetic setting. This generalization is made possible due to the recent discovery of logspace-uniform TC/sup 0/ circuits for iterated multiplication (A. Chiu et al., 2000). As an example of the sort of lower bounds that we obtain, we show that MAJ-MAJSAT is not contained in PrTiSp(n/sup 1+o(1)/, n/sup /spl epsiv//) for any /spl epsiv/<1. We also extend one of Fortnow's lower bounds, from showing that S~A~T~ does not have uniform NC/sup 1/ circuits of size n/sup 1+o(1)/, to a similar result for SAC/sup 1/ circuits.

We introduce a new notion of traversal sequences that we call exploration sequences. Exploration sequences share many properties with the traversal sequences defined in (AKL+), but they also exhibit some new properties. In particular, they have an ability to backtrack, and their random properties are robust under choice of the probability distribution on labels. Further, we present extremely simple constructions of polynomial length universal exploration sequences for some previously studied classes of graphs (e.g. 2-regular graphs, cliques, expanders), and we also present universal exploration sequences for trees. Our constructions beat previously known lower-bounds on the length of universal traversal sequences.