Unlike in TFNP, for which there is an abundance of problems capturing natural existence principles which are incomparable (in the black-box setting), Kleinberg et al. [Robert Kleinberg et al., 2021] observed that many of the natural problems considered so far in the second level of the total function polynomial hierarchy (TFΣ₂) reduce to the Strong Avoid problem. In this work, we prove that the Linear Ordering Principle does not reduce to Strong Avoid in the black-box setting, exhibiting the first TFΣ₂ problem that lies outside of the class of problems reducible to Strong Avoid. The proof of our separation exploits a connection between total search problems in the polynomial hierarchy and proof complexity, recently developed by Fleming, Imrek, and Marciot [Fleming et al., 2025]. In particular, this implies that to show our separation, it suffices to show that there is no small proof of the Linear Ordering Principle in a Σ₂-variant of the Sherali-Adams proof system. To do so, we extend the classical pseudo-expectation method to the Σ₂ setting, showing that the existence of a Σ₂ pseudo-expectation precludes a Σ₂ Sherali-Adams proof. The main technical challenge is in proving the existence of such a pseudo-expectation, we manage to do so by solving a combinatorial covering problem about permutations. We also show that the extended pseudo-expectation bound implies that the Linear Ordering Principle cannot be reduced to any problem admitting a low-degree Sherali-Adams refutation.

The space complexity of deterministic streaming algorithms for approximating the length of the longest increasing subsequence (LIS) in a string of length n has been known to be Θ̃(√n) for almost two decades. In contrast, the space complexity of this problem for randomized streaming algorithms remains one of the few longstanding open problems in one-pass streaming. In fact, no better than Ω(log n) lower bounds are known, and the best upper bounds are no better than their deterministic counterparts. In this paper, we push the limits of our understanding of the streaming space complexity of the approximate LIS length problem by studying it in the white-box adversarial streaming model. This model is an intermediate model between deterministic and randomized streaming algorithms that has recently attracted attention. In the white-box model, the streaming algorithm can draw fresh randomness when processing each incoming element, but an adversary generating the stream observes all previously used randomness and adaptively chooses the subsequent elements of the stream. We prove a tight (up to logarithmic factors) Ω(√n) space lower bound for any white-box streaming algorithm that approximates the length of the LIS of a stream of length n to within a factor better than 1.1. Thus, for this problem, white-box algorithms offer no improvement over deterministic ones.

This paper explores the previously studied measure called block number of Boolean functions, that counts the maximum possible number of minimal sensitive blocks for any input. We present close to tight upper bounds on the block number in terms of the function’s sensitivity and the allowed block size, improving previous bounds by a quadratic factor. Moreover, our bound on the block number yields sharper upper bounds on DNF size and decision tree size. For some functions, our upper bounds on decision tree size and DNF size are exponentially smaller than those obtained by previous methods. We obtain these results by introducing and estimating a novel measure called brick number, which not only upper bounds the block number but also leads to a new characterization of block sensitivity.

We introduce and study Certificate Game complexity, a measure of complexity based on the probability of winning a game where two players are given inputs with different function values and are asked to output some index i such that x_i≠ y_i, in a zero-communication setting. We give upper and lower bounds for private coin, public coin, shared entanglement and non-signaling strategies, and give some separations. We show that complexity in the public coin model is upper bounded by Randomized query and Certificate complexity. On the other hand, it is lower bounded by fractional and randomized certificate complexity, making it a good candidate to prove strong lower bounds on randomized query complexity. Complexity in the private coin model is bounded from below by zero-error randomized query complexity. The quantum measure highlights an interesting and surprising difference between classical and quantum query models. Whereas the public coin certificate game complexity is bounded from above by randomized query complexity, the quantum certificate game complexity can be quadratically larger than quantum query complexity. We use non-signaling, a notion from quantum information, to give a lower bound of n on the quantum certificate game complexity of the OR function, whose quantum query complexity is Θ(√n), then go on to show that this "non-signaling bottleneck" applies to all functions with high sensitivity, block sensitivity or fractional block sensitivity. We also consider the single-bit version of certificate games, where the inputs of the two players are restricted to having Hamming distance 1. We prove that the single-bit version of certificate game complexity with shared randomness is equal to sensitivity up to constant factors, thus giving a new characterization of sensitivity. On the other hand, the single-bit version of certificate game complexity with private randomness is equal to λ², where λ is the spectral sensitivity.

In this paper, we introduce a measure of Boolean functions we call diameter, that captures the relationship between certificate complexity and several other measures of Boolean functions. Our measure can be viewed as a variation on alternating number, but while alternating number can be exponentially larger than certificate complexity, we show that diameter is always upper bounded by certificate complexity. We argue that estimating diameter may help to get improved bounds on certificate complexity in terms of sensitivity, and other measures. Previous results due to Lin and Zhang [Krishnamoorthy Dinesh and Jayalal Sarma, 2018] imply that s(f) ≥ Ω(n^{1/3}) for transitive functions with constant alternating number. We improve and extend this bound and prove that s(f) ≥ √n for transitive functions with constant alternating number, as well as for transitive functions with constant diameter. {We also show that bs(f) ≥ Ω(n^{3/7}) for transitive functions under the weaker condition that the "minimum" diameter is constant.} Furthermore, we prove that the log-rank conjecture holds for functions of the form f(x ⊕ y) for functions f with diameter bounded above by a polynomial of the logarithm of the Fourier sparsity of the function f.

Comparator circuits are a natural circuit model for studying the concept of bounded fan-out computations, which intuitively corresponds to whether or not a computational model can make "copies" of intermediate computational steps. Comparator circuits are believed to be weaker than general Boolean circuits, but they can simulate Branching Programs and Boolean formulas. In this paper we prove the first superlinear lower bounds in the general (non-monotone) version of this model for an explicitly defined function. More precisely, we prove that the n-bit Element Distinctness function requires Ω((n/ log n)^(3/2)) size comparator circuits.

We define new functions based on the Andreev function and prove that they require n^{3}/polylog(n) formula size to compute. The functions we consider are generalizations of the Andreev function using compositions with the majority function. Our arguments apply to composing a hard function with any function that agrees with the majority function (or its negation) on the middle slices of the Boolean cube, as well as iterated compositions of such functions. As a consequence, we obtain n^{3}/polylog(n) lower bounds on the (non-monotone) formula size of an explicit monotone function by combining the monotone address function with the majority function.

Nisan and Szegedy [Nisan and Szegedy, 1994] conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a quadratic separation between block sensitivity and sensitivity. In this paper we give various new constructions of families of Boolean functions that exhibit quadratic separation between sensitivity and block sensitivity. Our constructions have several novel aspects. For example, we give the first direct constructions of families of Boolean functions that have both 0-block sensitivity and 1-block sensitivity quadratically larger than sensitivity.

Consider a large database of n data items that need to be stored using m servers. We study how to encode information so that a large number k of read requests can be performed in parallel, while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset batch codes introduced by Ishai et al. We give the families of multiset batch codes with asymptotically optimal rates of the form 1-1/poly(k) and a number of servers m scaling polynomially in the number of read requests k. An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graphtheoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close-to-optimal tradeoffs between the parameters for bipartite graph-based batch codes.

Consider a large database of n data items that need to be stored using m servers. We study how to encode information so that a large number k of read requests can be performed in parallel while the rate remains constant (and ideally approaches one). This problem is equivalent to the design of multiset Batch Codes introduced by Ishai, Kushilevitz, Ostrovsky and Sahai [1]. We give families of multiset batch codes with asymptotically optimal rates of the form 1 - 1/poly(k) and a number of servers m scaling polynomially in the number of read requests k. An advantage of our batch code constructions over most previously known multiset batch codes is explicit and deterministic decoding algorithms and asymptotically optimal fault tolerance. Our main technical innovation is a graph-theoretic method of designing multiset batch codes using dense bipartite graphs with no small cycles. We modify prior graph constructions of dense, high-girth graphs to obtain our batch code results. We achieve close to optimal tradeoffs between the parameters for bipartite graph based batch codes.

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.

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

Locally decodable codes are error correcting codes with the extra property that, in order to retrieve the correct value of just one position of the input with high probability, it is sufficient to read a small number of positions of the corresponding, possibly corrupted codeword. A breakthrough result by Yekhanin showed that 3-query linear locally decodable codes may have subexponential length. The construction of Yekhanin, and the three query constructions that followed, achieve correctness only up to a certain limit which is $1 - 3 delta$ for nonbinary codes, where an adversary is allowed to corrupt up to delta fraction of the codeword. The largest correctness for a subexponential length 3-query binary code is achieved in a construction by Woodruff, and it is below 1 - 3 delta. We show that achieving slightly larger correctness (as a function of $delta$) requires exponential codeword length for 3-query codes. Previously, there were no larger than quadratic lower bounds known for locally decodable codes with more than 2 queries, even in the case of 3-query linear codes. Our results hold for linear codes over arbitrary finite fields and for binary nonlinear codes. Considering larger number of queries, we obtain lower bounds for q-query codes for q>3, under certain assumptions on the decoding algorithm that have been commonly used in previous constructions. We also prove bounds on the largest correctness achievable by these decoding algorithms, regardless of the length of the code. Our results explain the limitations on correctness in previous constructions using such decoding algorithms. In addition, our results imply tradeoffs on the parameters of error correcting data structures.

We show that any deterministic streaming algorithm that makes a constant number of passes over the input and gives a constant factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space $\Omega(\sqrt{n})$. This proves a conjecture made by Gopalan et al. [Proceedings of the 18th Annual ACM–SIAM Symposium on Discrete Algorithms, 2007, pp. 318–327] who proved a matching upper bound. Our results yield asymptotically tight lower bounds for all approximation factors, thus resolving the main open problem from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.

We show that any deterministic data-stream algorithm that, makes a constant number of passes over the input and gives a constant, factor approximation of the length of the longest increasing subsequence in a sequence of length n must use space Omega(radicn). This proves a conjecture made by Gopalan, Jayram, Krauthgamer and Kumar |10| who proved a matching upper bound. Our results yield asymptotically tight tower bounds for all approximation factors, thus resolving the main open problem, from their paper. Our proof is based on analyzing a related communication problem and proving a direct sum type property for it.

We consider time-space tradeoffs for static data structure problems in the cell probe model with word size 1 (the bit probe model). In this model, the goal is to represent n-bit data with s=n+r bits such that queries (of a certain type) about the data can be answered by reading at most t bits of the representation. Ideally, we would like to keep both s and t small, but there are tradeoffs between the values of s and t that limit the possibilities of keeping both parameters small. In this paper, we consider the case of succinct representations, where s=n+r for some redundancy r≪n. For a Boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy–query time tradeoff of the form (r+1)t≥Ω(n/logn). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial properties of a coding theoretic flavor, and obtain (r+1)t≥Ω(n) for certain problems. Previously, no ω(m) lower bounds were known on t in the general model for explicit Boolean problems, even for very small redundancies. By restricting our attention to systematic or index structures ϕ satisfying ϕ(x)=x⋅ϕ∗(x) for some map ϕ∗ (where ⋅ denotes concatenation), we show similar lower bounds on the redundancy–query time tradeoff for the natural data structuring problems of Prefix Sum and Substring Search.

Preliminary versions of these papers appeared in the conference proceedings.The papers were selected by the Program Committee of the conference, chaired by Luca Trevisan.All papers were

Preliminary versions of these papers appeared in the conference proceedings.The papers were selected by the Program Committee of the conference, chaired by Luca Trevisan.All papers were refereed according to the journal's standards.This is the second part of the Special Issue; three papers already appeared in the first part, in issue 2 of volume 15.The four papers here include interesting results in the areas of time-space tradeoffs, multiparty communication complexity, derandomization and algebraic complexity.The three papers in the first part represent exciting developments in the areas of hardness of approximation, lower bound methods on classical and quantum computation, and connections between complexity theory and cryptography.This part contains the two award-winning papers of the conference: the 2005 Ronald V. Book Prize for Best Student Paper was given to Ryan Williams for his paper "Better Time-Space Lower Bounds for SAT and Related Problems", and the 2005 Best Paper Award was given to Ronen

We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least $\Omega(\log n)$ random bits are necessary for the t-private computation of the function {\tt xor} by n players for any $t \geq 2$. In view of the upper bound of O(t 2 log(n/t)) [E. Kushilevitz and Y. Mansour, SIAM J. Discrete Math., 10 (1997), pp. 647--661], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give a stronger lower bound of $\Omega(t \log(n/t))$. We note that all known randomness efficient private protocols designed specifically for {\tt xor} belong to this class. In fact we prove slightly stronger statements: we prove that on every input there is a run where the number of random bits used is large, rather than proving only that on some input there is a run where the number of random bits used is large. All our lower bounds hold for the "trusted dealer" model as well, and the $\Omega(t \log(n/t))$ lower bound for restricted protocols is tight, up to constant factors, for any $t \geq 2$ in this model. In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for {\tt xor} for any $2 \leq t = o(\log n)$. Our results also show that already for t=2$, $\Omega(\log n)$ random bits are necessary, while it is known that for the case of t=1$ a single random bit is sufficient for privately computing {\tt xor} for any number of players. Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.

In the cell probe model with word size 1 (the bit probe model), a static data structure problem is given by a map f : {0,1}^n * {0,1}^m -> {0,1}, where {0,1}^n is a set of possible data to be stored, {0,1}^m is a set of possible queries (for natural problems, we have m << n) and f(x,y) is the answer to question y about data x. A solution is given by a representation phi : {0,1}^n -> {0,1}^s and a query algorithm q so that q(phi(x), y) = f(x,y). The time t of the query algorithm is the number of bits it reads in phi(x). In this paper, we consider the case of succinct representations where s = n + r for some redundancy r << n. For a boolean version of the problem of polynomial evaluation with preprocessing of coefficients, we show a lower bound on the redundancy-query time trade-off of the form (r + 1) t >= Omega(n/log n). In particular, for very small redundancies r, we get an almost optimal lower bound stating that the query algorithm has to inspect almost the entire data structure (up to a logarithmic factor). We show similar lower bounds for problems satisfying a certain combinatorial property of a coding theoretic flavor. Previously, no omega(m) lower bounds were known on t in the general model for explicit functions, even for very small redundancies. By restricting our attention to systematic or index structures phi satisfying phi(x) = x · phi*(x) for some map phi* (where · denotes concatenation) we show similar lower bounds on the redundancy-query time trade-off for the natural data structuring problems of Prefix Sum and Substring Search.

We consider the amount of randomness necessary in information-theoretic private protocols. We prove that at least Ω(log n) random bits are necessary for the t-private computation of the function xor by n players, for any t ≥ 2. In view of the upper bound of O(t2log(n/t))[19], this bound is tight, up to constant factors, for any fixed t. For a class of protocols obeying certain restrictions, we give stronger lower bounds of Ω(t log (n/t)). We note that all known randomness efficient private protocols designed specifically for xor belong to this class. All our lower bounds hold for the "trusted dealer" model as well, and the Ω(t log (n/t)) lower bound for restricted protocols is tight, up to constant factors, for any t ≥ 2 in this model.In comparison, the previous lower bounds on the amount of randomness required by t-private computation of explicit functions did not grow with n for constant values of t, and our results improve the previous lower bounds for xor for any 2 ≤ t = o(log n). Our results also show that already for t = 2, Ω(log n) random bits are necessary, while it is known that for the case of t = 1 a single random bit is sufficient for privately computing xor for any number of players.Our proofs use novel techniques by which we extract random variables from a t-private protocol, and then use the t-privacy property of the protocol to prove properties of these random variables. These properties in turn imply that the number of random bits used by the players is large.

In the multiparty communication game (CFL game) of Chandra, Furst, and Lipton [Proceedings of the 15th Annual ACM Symposium on Theory of Computing, Boston, MA, 1983, pp. 94--99] k players collaboratively evaluate a function f(x 0 , . . . , x k -1) in which player i knows all inputs except xi. The players have unlimited computational power. The objective is to minimize communication. In this paper, we study the SIMULTANEOUS MESSAGES (SM) model of multiparty communication complexity. The SM model is a restricted version of the CFL game in which the players are not allowed to communicate with each other. Instead, each of the k players simultaneously sends a message to a referee, who sees none of the inputs. The referee then announces the function value. We prove lower and upper bounds on the SM complexity of several classes of explicit functions. Our lower bounds extend to randomized SM complexity via an entropy argument. A lemma establishing a tradeoff between average Hamming distance and range size for transformations of the Boolean cube might be of independent interest. Our lower bounds on SM complexity imply an exponential gap between the SM model and the CFL model for up to $(\log n)^{1-\epsilon}$ players for any $\epsilon > 0$. This separation is obtained by comparing the respective complexities of the Generalized Addressing Function, GAF G,k , where G is a group of order n. We also combine our lower bounds on SM complexity with the ideas of Håstad and Goldmann [Comput. Complexity, 1 (1991), pp. 113--129] to derive superpolynomial lower bounds for certain depth-2 circuits computing a function related to the GAF function. We prove some counterintuitive upper bounds on SM complexity. We show that {\sf GAF}$_{\mathbb{Z}_2^t,3}$ has SM complexity $O(n^{0.92})$. When the number of players is at least $c\log n$, for some constant c > 0, our SM protocol for {\sf GAF}$_{\mathbb{Z}_2^t,k}$ has polylog(n) complexity. We also examine a class of functions defined by certain depth-2 circuits. This class includes the Generalized Inner Product function and Majority of Majorities. When the number of players is at least 2+log n, we obtain polylog(n) upper bounds for this class of functions.

In this paper we prove a theorem that gives an (almost) tight upper bound on the sensitivity of a multiple-output Boolean function in terms of the sensitivity of its coordinates and the size of the range of the function. We apply this theorem to get improved lower bounds on the time (number of rounds) to compute Boolean functions by private protocols. These bounds are given in terms of the sensitivity of the function being computed and the amount of randomness used by the private protocol. These lower bounds are tight (up to constant factors) for the case of the xor function and together with the results in [E. Kushilevitz and A. Rosén, SIAM J. Discrete Math., 11 (1998), pp. 61--80.] establish a tight (up to constant factors) tradeoff between randomness and time in private computation.

We consider the question: Is finding just a part of a solution easier than finding the full solution? For example, is finding only an /spl epsiv/ fraction of the bits in a satisfying assignment to a 3-CNF formula easier than computing the whole assignment? For several important problems in NP we show that obtaining only a small fraction of the solution is as hard as finding the full solution. This can be interpreted in two ways: On the positive side, it is enough to look for an efficient algorithm that only recovers a small part of the solution, in order to completely solve any of these problems. On the negative side, any partial solution to these problems may be hard to find Some of our results can also be interpreted as robust proofs of membership.

Article A theorem on sensitivity and applications in private computation Share on Authors: Anna Gál Dept. of Computer Science, The University of Texas at Austin, Austin, TX Dept. of Computer Science, The University of Texas at Austin, Austin, TXView Profile , Adi Rosén Dept. of Computer Science, University of Toronto, Toronto, Canada Dept. of Computer Science, University of Toronto, Toronto, CanadaView Profile Authors Info & Claims STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of ComputingMay 1999 Pages 348–357https://doi.org/10.1145/301250.301340Online:01 May 1999Publication History 2citation235DownloadsMetricsTotal Citations2Total Downloads235Last 12 Months2Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

We consider the model of arithmetic branching programs, which is a generalization of modular branching programs. We show that, up to a polynomial factor in size, arithmetic branching programs are equivalent to complements of dependency programs. Using this equivalence we prove that dependency programs are closed under conjunction over every field. Furthermore, we show that span programs, an algebraic model of computation introduced by M. Karchmer and A. Wigderson (1993), are at least as strong as arithmetic programs; every arithmetic program can be simulated by a span program of size nod more than twice the size of the arithmetic program. Using the above results we give a new proof that NL/poly/spl sube//spl oplus/L/poly, first proved by A. Wigderson (1995). Our simulation of NL/poly is more efficient, and it holds for logspace counting classes over every field.

We give a characterization of span program size by a combinatorial-algebraic measure. The measure we consider is a generalization of a measure on covers which has been used to prove lower bounds on formula size and has also been studied with respect to communication complexity.In the monotone case our new methods yield nΩ(log n) lower bounds for the monotone span program complexity of explicit Boolean functions in n variables over arbitrary fields, improving the previous lower bounds on monotone span program size. Our characterization of span program size implies that any matrix with superpolynomial separation between its rank and cover number can be used to obtain superpolynomial lower bounds on monotone span program size. We also identify a property of bipartite graphs that is sufficient for constructing Boolean functions with large monotone span program complexity.

This paper contains two main results. The first is an explicit construction of bipartite graphs which do not contain certain complete bipartite subgraphs and have maximal density, up to a constant factor, under this constraint. This construction represents the first significant progress in three decades on this old problem in extremal graph theory. The construction beats the previously known probabilistic lower bound on density. The proof uses the elements of commutative algebra and algebraic geometry (theory of ideals, integral extensions, valuation rings). The second result concerns monotone span programs. We obtain the first superpolynomial lower bounds for explicit functions in this model. The best previous lower bound was $\Omega(n^{5/2})$ by Beimel, Gal, Paterson (FOCS’95); our analysis exploits a general combinatorial lower bound criterion from that paper. We give two proofs of superpolynomial lower bounds; one based on an analysis of Paley-type bipartitie graphs via Weil’s character sum estimates. A third result demonstrates the power of monotone span programs by exhibiting a function computable in this model in linear size while requiring superpolynomial size monotone circuits and exponential size monotone formulae.

Span programs provide a linear algebraic model of computation. Lower Bounds for span programs imply lower bounds for formula size, symmetric branching programs and for contact schemes. Monotone span programs correspond also to linear secret-sharing schemes. We present a technique for proving lower bounds for monotone span programs, and prove a lower bound of Ω(m/sup 2.5/) for the 6-clique function. Our results improve on the previously known bounds for explicit functions.

Proves that the reliable computation of any Boolean function with sensitivity s requires /spl Omega/(s log s) gates if the gates fail independently with a fixed positive probability. This theorem was stated by Dobrushin and Ortyukov (1977), but their proof was found by Pippenger, Stamoulis, and Tsitsiklis (1991) to contain some errors.>

It is proved that the reliable computation of any Boolean function with, sensitivity s requires Omega (s log s) gates if the gates of the circuit fail independently with a fixed positive probability. The Omega (s log s) bound holds even if s is the block sensitivity instead of the sensitivity of the Boolean function. Some open problems are mentioned.>