Anna Gál

TCS Journal 2023 Journal Article

Tight bounds on sensitivity and block sensitivity of some classes of transitive functions

• Siddhesh Chaubal
• Anna Gál

Nisan and Szegedy [18] conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. Until a recent breakthrough of Huang [15], the conjecture had been wide open in the general case, and was proved only for a few special classes of Boolean functions. Huang's result [15] implies that block sensitivity is at most the 4th power of sensitivity for any Boolean function. It remains open if a tighter relationship between sensitivity and block sensitivity holds for arbitrary Boolean functions; the largest known gap between these measures is quadratic [20, 23, 9, 12, 4, 10]. We prove tighter bounds showing that block sensitivity is at most 3rd power, and in some cases at most square of sensitivity for subclasses of transitive functions, defined by various properties of their DNF (or CNF) representation. Our results improve and extend previous results regarding transitive functions. We obtain these results by proving tight (up to constant factors) lower bounds on the smallest possible sensitivity of functions in these classes. In another line of research, the smallest possible block sensitivity of transitive functions has been closely examined. Our results yield tight (up to constant factors) lower bounds on the block sensitivity of the classes we consider.

MFCS Conference 2021 Conference Paper

Diameter Versus Certificate Complexity of Boolean Functions

• Siddhesh Chaubal
• Anna Gál

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.

I&C Journal 2016 Journal Article

A generalization of Spira's theorem and circuits with small segregators or separators

• Anna Gál
• Jing-Tang Jang

Spira showed that any Boolean formula of size s can be simulated in depth O ( log ⁡ s ). We generalize Spira's theorem and show that any Boolean circuit of size s with segregators (or separators) of size f ( s ) can be simulated in depth O ( f ( s ) log ⁡ s ). This improves and generalizes a simulation of polynomial-size Boolean circuits of constant treewidth k in depth O ( k 2 log ⁡ n ) by Jansen and Sarma. Our results imply that the class of languages computed by non-uniform families of polynomial-size circuits with constant size segregators equals non-uniform N C 1. As a corollary, we show that the Boolean Circuit Value problem for circuits with constant size segregators is in deterministic SPACE ( log 2 ⁡ n ). Our results also imply that the Planar Circuit Value problem, which is known to be P-Complete, is in SPACE ( n log ⁡ n ); and that the Layered Circuit Value and Synchronous Circuit Value problems, which are both P-complete, are in SPACE ( n ).

STOC Conference 2012 Conference Paper

Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates

• Anna Gál
• Kristoffer Arnsfelt Hansen
• Michal Koucký 0001
• Pavel Pudlák
• Emanuele Viola

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

TCS Journal 2009 Journal Article

Preface

• Anna Gál

FOCS Conference 2007 Conference Paper

Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence

• Anna Gál
• Parikshit Gopalan

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.

TCS Journal 2007 Journal Article

The cell probe complexity of succinct data structures

• Anna Gál
• Peter Bro Miltersen

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

MFCS Conference 2006 Conference Paper

On the Correlation Between Parity and Modular Polynomials

• Anna Gál
• Vladimir Trifonov

Abstract We consider the problem of bounding the correlation between parity and modular polynomials over ℤ q, for arbitrary odd integer q ≥3. We prove exponentially small upper bounds for classes of polynomials with certain linear algebraic properties. As a corollary, we obtain exponential lower bounds on the size necessary to compute parity by depth-3 circuits of certain form. Our technique is based on a new representation of the correlation using exponential sums. Our results include Goldmann’s result [Go] on the correlation between parity and degree one polynomials as a special case. Our general expression for representing correlation can be used to derive the bounds of Cai, Green, and Thierauf [CGT] for symmetric polynomials, using ideas of the [CGT] proof. The classes of polynomials for which we obtain exponentially small upper bounds include polynomials of large degree and with a large number of terms, that previous techniques did not apply to.

STOC Conference 2003 Conference Paper

Lower bounds on the amount of randomness in private computation

• Anna Gál
• Adi Rosén

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(t 2 log(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.

STOC Conference 1999 Conference Paper

A Theorem on Sensitivity and Applications in Private Computation

• Anna Gál
• Adi Rosén

STOC Conference 1998 Conference Paper

A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs

• Anna Gál

STOC Conference 1996 Conference Paper

Extremal Bipartite Graphs and Superpolynomial Lower Bounds for Monotone Span Programs

• László Babai
• Anna Gál
• János Kollár
• Lajos Rónyai
• Tibor Szabó
• Avi Wigderson

FOCS Conference 1995 Conference Paper

Lower Bounds for Monotone Span Programs

• Amos Beimel
• Anna Gál
• Mike Paterson

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.

FOCS Conference 1991 Conference Paper

Lower Bounds for the Complexity of Reliable Boolean Circuits with Noisy Gates

• Anna Gál

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