Nutan Limaye

MFCS Conference 2025 Conference Paper

#SAT-Algorithms for Classes of Threshold Circuits Based on Probabilistic Rank

• Nutan Limaye
• Adarsh Srinivasan
• Srikanth Srinivasan 0001

There is a large body of work that shows how to leverage lower bound techniques for circuit classes to obtain satisfiability algorithms that run in better than brute-force time [Ramamohan Paturi et al. , 1997; Ryan Williams, 2014]. For circuits with threshold gates, there are several such algorithms based on either - Probabilistic Representations by low-degree polynomials, which allow for the use of fast polynomial evaluation algorithms, or - Low rank, which allows for an efficient reduction to rectangular matrix multiplication. In this paper, we use a related notion of probabilistic rank to obtain satisfiability algorithms for circuit classes contained in ACC⁰∘3-PTF, i. e. constant-depth circuits with modular counting gates and a single layer of degree-3 polynomial threshold functions. Even for the special case of a single 3-PTF, it is not clear how to use either of the above two strategies to get a non-trivial satisfiability algorithm. The best known algorithm in this case previously was based on memoization and yields worse guarantees than our algorithm.

STOC Conference 2024 Conference Paper

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers

• Tuomas Hakoniemi
• Nutan Limaye
• Iddo Tzameret

Strong algebraic proof systems such as IPS (Ideal Proof System; Grochow-Pitassi ‍[J. ‍ACM, 65(6):37:1–55, 2018]) offer a general model for deriving polynomials in an ideal and refuting unsatisfiable propositional formulas, subsuming most standard propositional proof systems. A major approach for lower bounding the size of IPS refutations is the Functional Lower Bound Method (Forbes, Shpilka, Tzameret and Wigderson ‍[Theory ‍Comput., 17: 1-88, 2021]), which reduces the hardness of refuting a polynomial equation f ( x )=0 with no Boolean solutions to the hardness of computing the function 1/ f ( x ) over the Boolean cube with an algebraic circuit. Using symmetry we provide a general way to obtain many new hard instances against fragments of IPS via the functional lower bound method. This includes hardness over finite fields and hard instances different from Subset Sum variants both of which were unknown before, and stronger constant-depth lower bounds. Conversely, we expose the limitation of this method by showing it cannot lead to proof complexity lower bounds for any hard Boolean instance (e.g., CNFs) for any sufficiently strong proof systems. Specifically, we show the following: Nullstellensatz degree lower bounds using symmetry : Extending [Forbes et al . ‍Theory Comput., 17: 1-88, 2021] we show that every unsatisfiable symmetric polynomial with n variables requires degree > n refutations (over sufficiently large characteristic). Using symmetry again, by characterising the n /2-homogeneous slice appearing in refutations, we show that unsatisfiable invariant polynomials of degree n /2 require degree ≥ n refutations. Lifting to size lower bounds : Lifting our Nullstellensatz degree bounds to IPS-size lower bounds, we obtain exponential lower bounds for any poly-logarithmic degree symmetric instance against IPS refutations written as oblivious read-once algebraic programs (roABP-IPS). For invariant polynomials, we show lower bounds against roABP-IPS and refutations written as multilinear formulas in the placeholder IPS regime (studied by Andrews and Forbes [54th Ann. ‍Symp. ‍Theory ‍Comput., STOC 2022]), where the hard instances do not necessarily have small roABPs themselves, including over positive characteristic fields. This provides the first IPS-fragment lower bounds over finite fields. By an adaptation of the work of Amireddy, Garg, Kayal, Saha and Thankey ‍[50th Intl. ‍Colloq. ‍Aut. ‍Lang. ‍Prog., ICALP 2023], we strengthen the constant-depth IPS lower bounds obtained recently in Govindasamy, Hakoniemi and Tzameret ‍[63rd IEEE Ann. ‍Symp. ‍Found. ‍Comput. ‍Sci., FOCS 2022]. Barriers for Boolean instances : While lower bounds against strong propositional proof systems were the original motivation for studying algebraic proof systems in the 1990s [Beame et al. ‍Proc. ‍London Math. ‍Soc. ‍(3) 73, 1 (1996), 1–26; Buss et al. ‍Computational Complexity 6, 3 (1996), 256–298] we show that the functional lower bound method alone cannot establish any size lower bound for Boolean instances for any sufficiently strong proof systems, and in particular, cannot lead to lower bounds against AC 0 [ p ]-Frege and TC 0 -Frege.

STOC Conference 2024 Conference Paper

On the Power of Homogeneous Algebraic Formulas

• Hervé Fournier
• Nutan Limaye
• Srikanth Srinivasan 0001
• Sébastien Tavenas

STOC Conference 2022 Conference Paper

Set-multilinear and non-commutative formula lower bounds for iterated matrix multiplication

• Sébastien Tavenas
• Nutan Limaye
• Srikanth Srinivasan 0001

An Algebraic Formula for a polynomial P ∈ [ x 1 ,…, x N ] is an algebraic expression for P ( x 1 ,…, x N ) using variables, field constants, additions and multiplications. Such formulas capture an algebraic analog of the Boolean complexity class NC 1 . Proving lower bounds against this model is thus an important problem. It is known that, to prove superpolynomial lower bounds against algebraic formulas, it suffices to prove good enough lower bounds against restricted kinds of formulas known as Set-Multilinear formulas, for computing a polynomial P ( x 1 ,..., x N ) of degree O (log N /loglog N ). In the past, many superpolynomial lower bounds were found, but they are of the form Ω( f ( d ) poly( N )) (where f is typically a subexponential function) which is insufficient to get lower bounds for general formulas. Recently, the authors proved the first non-FPT lower bounds, i.e., a lower bound of the form N Ω( f ( d )) , against small-depth set-multilinear formulas (and also for circuits). In this work, we extend this result in two directions. Large-depth set-multilinear formulas. In the setting of general set-multilinear formulas, we prove a lower bound of (log n ) Ω(log d ) for computing the Iterated Matrix Multiplication polynomial IMM n , d . In particular, this implies the first superpolynomial lower bound against unbounded-depth set-multilinear formulas computing IMM n , n . As a corollary, this resolves the homogeneous version of a question of Nisan (asked in 1991) regarding the relative power of Algebraic formulas and Branching programs in the non-commutative setting. Stronger bounds for homogeneous non-commutative small-depth circuits. In the small-depth homogeneous non-commutative case, we prove a lower bound of n d 1/Δ /2 O (Δ) , which yields non-FPT bounds for depths up to o (√log d ). In comparison, our previous bound works in the harder commutative set-multilinear setting, but only up to depths o (loglog d ). Moreover, our lower bound holds for all values of d , as opposed to the previous set-multilinear lower bound, which holds as long as d is small, i.e., d = O (log n ).

FOCS Conference 2021 Conference Paper

Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

• Nutan Limaye
• Srikanth Srinivasan 0001
• Sébastien Tavenas

An Algebraic Circuit for a polynomial $P\ \ \in \mathbb{F}[x_{1}, \ldots, x_{N}]$ is a computational model for constructing the polynomial $P$ using only additions and multiplications. It is a syntactic model of computation, as opposed to the Boolean Circuit model, and hence lower bounds for this model are widely expected to be easier to prove than lower bounds for Boolean circuits. Despite this, we do not have superpolynomial lower bounds against general algebraic circuits of depth 3 (except over constant-sized finite fields) and depth 4 (over fields other than $\mathbb{F}_{2}$ ), while constant-depth Boolean circuit lower bounds have been known since the early 1980s. In this paper, we prove the first super polynomial lower bounds against general algebraic circuits of all constant depths over all fields of characteristic 0 (or large). We also prove the first lower bounds against homogeneous algebraic circuits of constant depth over any field. Our approach is surprisingly simple. We first prove superpolynomial lower bounds for constant-depth Set-Multilinear circuits. While strong lower bounds were already known against such circuits, most previous lower bounds were of the form $f(d)\cdot \text{poly}(N)$, where $d$ denotes the degree of the polynomial. In analogy with Parameterized complexity, we call this an FPT lower bound. We extend a well-known technique of Nisan and Wigderson (FOCS 1995) to prove non-FPT lower bounds against constant-depth set-multilinear circuits computing the Iterated Matrix Multiplication polynomial $\text{IMM}_{n, d}$ (which computes a fixed entry of the product of $d\ n\times n$ matrices). More precisely, we prove that any set-multilinear circuit of depth $\Delta$ computing $\text{IMM}_{n, d}$ must have size at least $n^{d^{\exp(-O(\Delta))}}$. This result holds over any field, as long as $d=o(\log n)$. We then show how to convert any constant-depth algebraic circuit of size $s$ to a constant-depth set-multilinear circuit with a blow-up in size that is exponential in $d$ but only polynomial in $s$ over fields of characteristic 0. (For depths greater than 3, previous results of this form increased the depth of the resulting circuit to $\Omega(\log s))$. This implies our constant-depth circuit lower bounds. Finally, we observe that our superpolynomial lower bound for constant-depth circuits implies the first deterministic sub-exponential time algorithm for solving the Polynomial Identity Testing (PIT) problem for all small depth circuits using the known connection between algebraic hardness and randomness.

Highlights Conference 2021 Conference Abstract

Word polynomials and algebraic circuit lower bounds

• Nutan Limaye

Polynomials are ubiquitous objects which we encounter in mathematics, life sciences, and computation. An algebraic circuit is a model of computation of polynomials. It consists of addition and multiplication gates, connected through a DAG structure that takes variables and constants as inputs and outputs a polynomial. The size of the algebraic circuits is the number of addition and multiplication gates it uses. One way to understand the complexity of computing polynomials is to obtain bounds on the sizes of the circuits needed to compute them. This complexity theoretical study was initiated by Leslie Valiant in 1979 as a route towards attacking the famous P vs. NP problem. In this talk, we will look at polynomials inspired by automata-theoretic ideas, which we will call word polynomials. We will show how they have helped in proving strong lower bounds. In fact, in our recent work, these polynomials were used to prove the first superpolynomial lower bound for reasonably general models of computation. This talk is based on joint works with Guillaume Lagarde, Guillaume Malod, Srikanth Srinivasan, and Sébastien Tavenas.

TCS Journal 2020 Journal Article

Skew circuits of small width

• Nikhil Balaji
• Andreas Krebs
• Nutan Limaye

A celebrated result of Barrington (1985) proved that polynomial size, width-5 branching programs (BP) are equivalent in power to a restricted form of branching programs – polynomial sized width-5 permutation branching programs (PBP), which in turn capture all of NC 1. On the other hand it is known that width-3 PBPs require exponential size to compute the AND function. No such lower bound is known for width-4 PBPs, however it is widely conjectured that width-4 PBPs will not capture all of NC 1. In this work, we study the power of bounded width branching programs by comparing them with bounded width skew circuits. It is well known that branching programs of bounded width have the same power as skew circuit of bounded width. The naive approach converts a BP of width w to a skew circuit of width w 2. We improve this bound and show that BP of width w ≥ 5 can be converted to a skew circuit of width 7. This also implies that skew circuits of bounded width are equal in power to skew circuits of width 7. For the other way, we prove that for any w ≥ 2, a skew circuit of width w can be converted into an equivalent branching program of width w. We prove that width-2 skew circuits are not universal while width-3 skew circuits are universal and that any polynomial sized CNF or DNF is computable by width 3 skew circuits of polynomial size. It is known that Parity does not have small CNFs or DNFs. It is easy to see that Parity has width-4 skew circuits. We prove that a width-3 skew circuit computing Parity requires exponential size. This gives an exponential separation between the power of width-3 skew circuits and width-4 skew circuits.

STOC Conference 2019 Conference Paper

A fixed-depth size-hierarchy theorem for AC 0 [⊕] via the coin problem

• Nutan Limaye
• Karteek Sreenivasaiah
• Srikanth Srinivasan 0001
• Utkarsh Tripathi
• S. Venkitesh

In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC 0 [⊕]. In particular, we show that for any fixed d , the class C d , k of functions that have uniform AC 0 [⊕] formulas of depth d and size n k form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC 0 [⊕] formulas. The explicit functions are derived from the δ -Coin Problem , which is the computational problem of distinguishing between coins that are heads with probability (1+δ)/2 or (1−δ)/2, where δ is a parameter that is going to 0. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Upper bounds. For any constant d ≥ 2, we show that there are explicit monotone AC 0 formulas (i.e. made up of AND and OR gates only) solving the δ-coin problem that have depth d , size exp( O ( d (1/δ) 1/( d −1) )), and sample complexity (i.e. number of inputs) poly(1/δ). This matches previous upper bounds of O’Donnell and Wimmer (ICALP 2007) and Amano (ICALP 2009) in terms of size (which is optimal) and improves the sample complexity from exp( O ( d (1/δ) 1/( d −1) )) to poly(1/δ). Lower bounds. We show that the above upper bounds are nearly tight (in terms of size) even for the significantly stronger model of AC 0 [⊕] formulas (which are also allowed NOT and Parity gates): formally, we show that any AC 0 [⊕] formula solving the δ-coin problem must have size exp(Ω( d (1/δ) 1/( d −1) )). This strengthens a result of Shaltiel and Viola (SICOMP 2010), who prove a exp(Ω((1/δ) 1/( d +2) )) lower bound for AC 0 [⊕], and a lower bound of exp(Ω((1/δ) 1/( d −1) )) shown by Cohen, Ganor and Raz (APPROX-RANDOM 2014) for the class 0 . The upper bound is a derandomization involving a use of Janson’s inequality and classical combinatorial designs. The lower bound involves proving an optimal degree lower bound for polynomials over 2 solving the δ-coin problem.

FOCS Conference 2018 Conference Paper

A Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear Circuits

• Suryajith Chillara
• Christian Engels
• Nutan Limaye
• Srikanth Srinivasan 0001

We study the size blow-up that is necessary to convert an algebraic circuit of product-depth δ+1 to one of product-depth δ in the multilinear setting. We show that for every positive δ = δ(n) = o(log n/log log n), there is an explicit multilinear polynomial P^(δ) on n variables that can be computed by a multilinear formula of product-depth δ+1 and size O(n), but not by any multilinear circuit of product-depth δ and size less than exp(n^Ω(1/δ)). This result is tight up to the constant implicit in the double exponent for all δ = o(log n/log log n). This strengthens a result of Raz and Yehudayoff (Computational Complexity 2009) who prove a quasipolynomial separation for constant-depth multilinear circuits, and a result of Kayal, Nair and Saha (STACS 2016) who give an exponential separation in the case δ = 1. Our separating examples may be viewed as algebraic analogues of variants of the Graph Reachability problem studied by Chen, Oliveira, Servedio and Tan (STOC 2016), who used them to prove lower bounds for constant-depth Boolean circuits.

MFCS Conference 2017 Conference Paper

Lower Bounds and PIT for Non-Commutative Arithmetic Circuits with Restricted Parse Trees

• Guillaume Lagarde
• Nutan Limaye
• Srikanth Srinivasan 0001

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring F<x_1, .. ., x_N>, where variables do not commute. We consider circuits that are restricted in the ways in which they can compute monomials: this can be seen as restricting the families of parse trees that appear in the circuit. Such restrictions capture essentially all non-commutative circuit models for which lower bounds are known. We prove several results about such circuits. - We show explicit exponential lower bounds for circuits with up to an exponential number of parse trees, strengthening the work of Lagarde, Malod, and Perifel (ECCC 2016), who prove such a result for Unique Parse Tree (UPT) circuits which have a single parse tree. - We show explicit exponential lower bounds for circuits whose parse trees are rotations of a single tree. This simultaneously generalizes recent lower bounds of Limaye, Malod, and Srinivasan (Theory of Computing 2016) and the above lower bounds of Lagarde et al. , which are known to be incomparable. - We make progress on a question of Nisan (STOC 1991) regarding separating the power of Algebraic Branching Programs (ABPs) and Formulas in the non-commutative setting by showing a tight lower bound of n^{Omega(log d)} for any UPT formula computing the product of d n*n matrices. When d <= log n, we can also prove superpolynomial lower bounds for formulas with up to 2^{o(d)} many parse trees (for computing the same polynomial). Improving this bound to allow for 2^{O(d)} trees would yield an unconditional separation between ABPs and Formulas. - We give deterministic white-box PIT algorithms for UPT circuits over any field (strengthening a result of Lagarde et al. (2016)) and also for sums of a constant number of UPT circuits with different parse trees.

FOCS Conference 2014 Conference Paper

An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas

• Neeraj Kayal
• Nutan Limaye
• Chandan Saha 0001
• Srikanth Srinivasan 0001

We show here a 2Ω(√d ⋅ log N) size lower bound for homogeneous depth four arithmetic formulas. That is, we give an explicit family of polynomials of degree d on N variables (with N = d3 in our case) with 0, 1-coefficients such that for any representation of a polynomial f in this family of the form f = Σi ∏j Qij, where the Qij's are homogeneous polynomials (recall that a polynomial is said to be homogeneous if all its monomials have the same degree), it must hold that ∑i, j (Number of monomials of Qij)) ≥2Ω(√d ⋅log N). The above mentioned family, which we refer to as the Nisan-Wigderson design-based family of polynomials, is in the complexity class VNP. Our work builds on recent lower bound results [1], [2], [3], [4], [5] and yields an improved quantitative bound as compared to the quasi-polynomial lower bound from an earlier work of the same authors and the NΩ(log log N) lower bound in the independent work of [7].

STOC Conference 2014 Conference Paper

Lower bounds for depth 4 formulas computing iterated matrix multiplication

• Hervé Fournier
• Nutan Limaye
• Guillaume Malod
• Srikanth Srinivasan 0001

We study the arithmetic complexity of iterated matrix multiplication. We show that any multilinear homogeneous depth 4 arithmetic formula computing the product of d generic matrices of size n × n , IMM n,d , has size n Ω(√ d ) as long as d = n O (1) . This improves the result of Nisan and Wigderson (Computational Complexity, 1997) for depth 4 set-multilinear formulas. We also study ΣΠ [ O ( d / t )] ΣΠ [ t ] formulas, which are depth 4 formulas with the stated bounds on the fan-ins of the Π gates. A recent depth reduction result of Tavenas (MFCS, 2013) shows that any n -variate degree d = n O (1) polynomial computable by a circuit of size poly( n ) can also be computed by a depth 4 ΣΠ [ O ( d / t )] ΣΠ [ t ] formula of top fan-in n O ( d / t ) . We show that any such formula computing IMM n,d has top fan-in n Ω( d / t ) , proving the optimality of Tavenas' result. This also strengthens a result of Kayal, Saha, and Saptharishi (ECCC, 2013) which gives a similar lower bound for an explicit polynomial in VNP.

STOC Conference 2014 Conference Paper

Super-polynomial lower bounds for depth-4 homogeneous arithmetic formulas

• Neeraj Kayal
• Nutan Limaye
• Chandan Saha 0001
• Srikanth Srinivasan 0001

We show that any depth-4 homogeneous arithmetic formula computing the Iterated Matrix Multiplication polynomial IMM n,d -- the (1, 1)-th entry of the product of d generic n × n matrices -- has size n Ω(log n ), if d = Ω (log 2 n ). More-over, any depth-4 homogeneous formula computing the determinant polynomial Det n -- the determinant of a generic n × n matrix -- has size n Ω(log n ) .

MFCS Conference 2013 Conference Paper

Small Depth Proof Systems

• Andreas Krebs
• Nutan Limaye
• Meena Mahajan
• Karteek Sreenivasaiah

Abstract A proof system for a language L is a function f such that Range( f ) is exactly L. In this paper, we look at proof systems from a circuit complexity point of view and study proof systems that are computationally very restricted. The restriction we study is: they can be computed by bounded fanin circuits of constant depth (NC 0 ), or of O (loglog n ) depth but with O (1) alternations (poly log AC 0 ). Each output bit depends on very few input bits; thus such proof systems correspond to a kind of local error-correction on a theorem-proof pair. We identify exactly how much power we need for proof systems to capture all regular languages. We show that all regular language have poly log AC 0 proof systems, and from a previous result (Beyersdorff et al, MFCS 2011, where NC 0 proof systems were first introduced), this is tight. Our technique also shows that Maj has poly log AC 0 proof system. We explore the question of whether Taut has NC 0 proof systems. Addressing this question about 2TAUT, and since 2TAUT is closely related to reachability in graphs, we ask the same question about Reachability. We show that both Undirected Reachability and Directed UnReachability have NC 0 proof systems, but Directed Reachability is still open. In the context of how much power is needed for proof systems for languages in NP, we observe that proof systems for a good fraction of languages in NP do not need the full power of AC 0; they have SAC 0 or coSAC 0 proof systems.

TCS Journal 2013 Journal Article

Streaming algorithms for language recognition problems

• Ajesh Babu
• Nutan Limaye
• Jaikumar Radhakrishnan
• Girish Varma

We study the complexity of the following problems in the streaming model. Membership testing for DLIN. We show that every language in DLIN can be recognized by a randomized one-pass O ( log n ) space algorithm with an inverse polynomial one-sided error and by a deterministic p -pass O ( n / p ) space algorithm. We show that these algorithms are optimal. Membership testing for LL ( k ). For languages generated by LL ( k ) grammars with a bound of r on the number of nonterminals at any stage in the left-most derivation, we show that membership can be tested by a randomized one-pass O ( r log n ) space algorithm with an inverse polynomial (in n ) one-sided error. Membership testing for DCFL. We show that randomized algorithms as efficient as the ones described above for DLIN and LL ( k ) (which are subclasses of DCFL) cannot exist for all of DCFL: there is a language in VPL (a subclass of DCFL) for which any randomized p -pass algorithm with an error bounded by ϵ < 1 / 2 must use Ω ( n / p ) space. Degree sequence problem. We study the problem of determining, given a sequence d 1, d 2, …, d n and a graph G, whether the degree sequence of G is precisely d 1, d 2, …, d n. We give a randomized one-pass O ( log n ) space algorithm with an inverse polynomial one-sided error probability. We show that our algorithms are optimal. Our randomized algorithms are based on the recent work of Magniez et al. [1]; our lower bounds are obtained by considering related communication complexity problems.

MFCS Conference 2011 Conference Paper

Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions

• Andreas Krebs
• Nutan Limaye
• Srikanth Srinivasan 0001

Abstract We study the streaming complexity of the membership problem of \(1\mbox{-turn-}\mbox{\sf Dyck}_2\) and \(\mbox{\sf Dyck}_2\) when there are a few errors in the input string. \(1\mbox{-turn-}\mbox{\sf Dyck}_2\) with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string \(x' \in 1\mbox{-turn-}\mbox{\sf Dyck}_2\) such that x is obtained by flipping at most k locations of x ′ using: O ( k log n ) space, O ( k log n ) randomness, and \(\mathop{\mathrm{poly}}(k \log n)\) time per item and with error at most 1/ n Ω(1). O ( k 1 + ε + log n ) space for every 0 ≤ ε ≤ 1, O (log n ) randomness, O ((log O (1) n + k O (1) )) time per item, with error at most 1/8. Here, we also prove that any randomized one-pass algorithm that makes error at most k / n requires at least Ω( k log( n / k )) space to accept strings which are exactly k -away from strings in \(1\mbox{-turn-}\mbox{\sf Dyck}_2\) and to reject strings which are exactly k + 2-away from strings in \(1\mbox{-turn-}\mbox{\sf Dyck}_2\). Since \(1\mbox{-turn-}\mbox{\sf Dyck}_2\) and the Hamming Distance problem are closely related we also obtain new upper and lower bounds for this problem. \(\mbox{\sf Dyck}_2\) with errors: We prove that there exists a randomized one-pass algorithm that given x checks whether there exists a string \(x' \in \mbox{\sf Dyck}_2\) such that x is obtained from x ′ by changing (in some restricted manner) at most k positions using: \(O(k \log n + \sqrt{n \log n})\) space, O ( k log n ) randomness, \(\mathop{\mathrm{poly}}(k \log n)\) time per element and with error at most 1/ n Ω(1). \(O(k^{1+\epsilon}+ \sqrt{n \log n})\) space for every 0 < ε ≤ 1, O (log n ) randomness, O ((log O (1) n + k O (1) )) time per element, with error at most 1/8.