Search Results

Documents authored by Gál, Anna

Found 2 Possible Name Variants:

Gal, Anna

Document
DOI: 10.4230/DagRep.13.3.17
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)

Authors: Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar

Published in: Dagstuhl Reports, Volume 13, Issue 3 (2023)

Abstract
This report documents the program and activities of Dagstuhl Seminar 23111 "Computational Complexity of Discrete Problems", which was held in-person in March 2023 (the previous instance of the seminar series had been held online in March 2021). Following a description of the seminar’s objectives and its overall organization, this report lists the different major talks given during the seminar in alphabetical order of speakers, followed by the abstracts of the talks, including the main references and relevant sources where applicable. The return to an in-person setting allowed an intense atmosphere of active research and interaction throughout the five day seminar.
Cite as

Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar. Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). In Dagstuhl Reports, Volume 13, Issue 3, pp. 17-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.13.3.17,
  author =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)}},
  pages =	{17--31},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{3},
  editor =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.3.17},
  URN =		{urn:nbn:de:0030-drops-192261},
  doi =		{10.4230/DagRep.13.3.17},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.32
Certificate Games

Authors: Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
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.
Cite as

Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny. Certificate Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.32,
  author =	{Chakraborty, Sourav and G\'{a}l, Anna and Laplante, Sophie and Mittal, Rajat and Sunny, Anupa},
  title =	{{Certificate Games}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{32:1--32:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-175353},
  doi =		{10.4230/LIPIcs.ITCS.2023.32},
  annote =	{Keywords: block sensitivity, boolean function complexity, certificate complexity, query complexity, sensitivity, zero-communication two-player games}
}
Document
DOI: 10.4230/DagRep.11.2.1
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)

Authors: Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau

Published in: Dagstuhl Reports, Volume 11, Issue 2 (2021)

Abstract
This report documents the program and activities of Dagstuhl Seminar 21121 "Computational Complexity of Discrete Problems," which was held online in March 2021. Starting with a description of the organization of the online meeting and the topics covered, we then list the different talks given during the seminar in alphabetical order of speakers, followed by the abstracts of the talks, including the main references and relevant sources where applicable. Despite the fact that only a compressed daily time slot was available for the seminar with participants from time zones spanning the whole globe and despite the fact that informal discussions were harder to hold than in a typical on-site seminar, the rate of participation throughout the seminar was very high and many lively scientific debates were held.
Cite as

Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). In Dagstuhl Reports, Volume 11, Issue 2, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.11.2.1,
  author =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)}},
  pages =	{1--16},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{2},
  editor =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.2.1},
  URN =		{urn:nbn:de:0030-drops-146836},
  doi =		{10.4230/DagRep.11.2.1},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.31
Diameter Versus Certificate Complexity of Boolean Functions

Authors: Siddhesh Chaubal and Anna Gál

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
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.
Cite as

Siddhesh Chaubal and Anna Gál. Diameter Versus Certificate Complexity of Boolean Functions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chaubal_et_al:LIPIcs.MFCS.2021.31,
  author =	{Chaubal, Siddhesh and G\'{a}l, Anna},
  title =	{{Diameter Versus Certificate Complexity of Boolean Functions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.31},
  URN =		{urn:nbn:de:0030-drops-144713},
  doi =		{10.4230/LIPIcs.MFCS.2021.31},
  annote =	{Keywords: Sensitivity Conjecture, Boolean Functions, Certificate Complexity, Block Sensitivity, Log-rank Conjecture, Alternating Number}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.58
Lower Bounds for (Non-Monotone) Comparator Circuits

Authors: Anna Gál and Robert Robere

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
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.
Cite as

Anna Gál and Robert Robere. Lower Bounds for (Non-Monotone) Comparator Circuits. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.ITCS.2020.58,
  author =	{G\'{a}l, Anna and Robere, Robert},
  title =	{{Lower Bounds for (Non-Monotone) Comparator Circuits}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.58},
  URN =		{urn:nbn:de:0030-drops-117431},
  doi =		{10.4230/LIPIcs.ITCS.2020.58},
  annote =	{Keywords: comparator circuits, circuit complexity, Nechiporuk, lower bounds}
}
Document
DOI: 10.4230/DagRep.9.3.64
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)

Authors: Anna Gál, Rahul Santhanam, and Till Tantau

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
The following report archives the presentations and activities of the March 2019 Dagstuhl Seminar 19121 "Computational Complexity of Discrete Problems". Section 1 summarizes the topics and some specific results offered in selected talks during the course of the week. Section 2 provides a table of contents, listing each of the talks given in alphabetical order. Section 3 contains the abstracts, indicating both the main reference and other relevant sources (where applicable) to allow the reader to investigate the topics further.
Cite as

Anna Gál, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). In Dagstuhl Reports, Volume 9, Issue 3, pp. 64-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.9.3.64,
  author =	{G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)}},
  pages =	{64--82},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.64},
  URN =		{urn:nbn:de:0030-drops-112920},
  doi =		{10.4230/DagRep.9.3.64},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, parametrisation, randomness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.35
Cubic Formula Size Lower Bounds Based on Compositions with Majority

Authors: Anna Gál, Avishay Tal, and Adrian Trejo Nuñez

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
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.
Cite as

Anna Gál, Avishay Tal, and Adrian Trejo Nuñez. Cubic Formula Size Lower Bounds Based on Compositions with Majority. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.ITCS.2019.35,
  author =	{G\'{a}l, Anna and Tal, Avishay and Trejo Nu\~{n}ez, Adrian},
  title =	{{Cubic Formula Size Lower Bounds Based on Compositions with Majority}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.35},
  URN =		{urn:nbn:de:0030-drops-101283},
  doi =		{10.4230/LIPIcs.ITCS.2019.35},
  annote =	{Keywords: formula lower bounds, random restrictions, KRW conjecture, composition}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.13
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Authors: Siddhesh Chaubal and Anna Gál

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
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.
Cite as

Siddhesh Chaubal and Anna Gál. New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chaubal_et_al:LIPIcs.FSTTCS.2018.13,
  author =	{Chaubal, Siddhesh and G\'{a}l, Anna},
  title =	{{New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.13},
  URN =		{urn:nbn:de:0030-drops-99129},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.13},
  annote =	{Keywords: Sensitivity Conjecture, Boolean Functions, Complexity Measures}
}
Document
DOI: 10.4230/DagRep.7.3.45
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)

Authors: Anna Gál, Michal Koucký, Oded Regev, and Till Tantau

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in alphabetical order. The last section contains the abstracts of the talks.
Cite as

Anna Gál, Michal Koucký, Oded Regev, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). In Dagstuhl Reports, Volume 7, Issue 3, pp. 45-69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.7.3.45,
  author =	{G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)}},
  pages =	{45--69},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.45},
  URN =		{urn:nbn:de:0030-drops-73611},
  doi =		{10.4230/DagRep.7.3.45},
  annote =	{Keywords: Computational Complexity}
}
Document
DOI: 10.4230/DagRep.4.3.62
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)

Authors: Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk

Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in chronological order. The last section contains the abstracts of the talks.
Cite as

Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk. Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). In Dagstuhl Reports, Volume 4, Issue 3, pp. 62-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.4.3.62,
  author =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)}},
  pages =	{62--84},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{3},
  editor =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.62},
  URN =		{urn:nbn:de:0030-drops-45921},
  doi =		{10.4230/DagRep.4.3.62},
  annote =	{Keywords: discrete problems, computational complexity, Turing machines, Boolean circuits, arithmetic circuits, quantum computing, communication complexity, pseudorandomness, derandomization, approximation, data streams}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.673
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Authors: Anna Gal and Andrew Mills

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
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.
Cite as

Anna Gal and Andrew Mills. Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 673-684, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.STACS.2011.673,
  author =	{Gal, Anna and Mills, Andrew},
  title =	{{Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{673--684},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.673},
  URN =		{urn:nbn:de:0030-drops-30534},
  doi =		{10.4230/LIPIcs.STACS.2011.673},
  annote =	{Keywords: error correcting codes}
}
Document
DOI: 10.4230/DagSemProc.06111.10
Incremental branching programs

Authors: Anna Gál, Pierre McKenzie, and Michal Koucký

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We propose a new model of restricted branching programs which we call {em incremental branching programs}. We show that {em syntactic} incremental branching programs capture previously studied structured models of computation for the problem GEN, namely marking machines [Cook74]. and Poon's extension [Poon93] of jumping automata on graphs [CookRackoff80]. We then prove exponential size lower bounds for our syntactic incremental model, and for some other restricted branching program models as well. We further show that nondeterministic syntactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN subproblem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems. Joint work with Anna Gál and Michal Koucký
Cite as

Anna Gál, Pierre McKenzie, and Michal Koucký. Incremental branching programs. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:DagSemProc.06111.10,
  author =	{G\'{a}l, Anna and McKenzie, Pierre and Kouck\'{y}, Michal},
  title =	{{Incremental branching programs}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.10},
  URN =		{urn:nbn:de:0030-drops-6230},
  doi =		{10.4230/DagSemProc.06111.10},
  annote =	{Keywords: Complexity theory, branching programs, logarithmic space, marking machines}
}
Document
DOI: 10.4230/DagSemProc.06111.9
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity

Authors: Jeff Ford and Anna Gál

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We develop a new method for estimating the discrepancy of tensors associated with multiparty communication problems in the ``Number on the Forehead'' model of Chandra, Furst and Lipton. We define an analogue of the Hadamard property of matrices for tensors in multiple dimensions and show that any $k$-party communication problem represented by a Hadamard tensor must have $Omega(n/2^k)$ multiparty communication complexity. We also exhibit constructions of Hadamard tensors, giving $Omega(n/2^k)$ lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions.
Cite as

Jeff Ford and Anna Gál. Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ford_et_al:DagSemProc.06111.9,
  author =	{Ford, Jeff and G\'{a}l, Anna},
  title =	{{Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.9},
  URN =		{urn:nbn:de:0030-drops-6076},
  doi =		{10.4230/DagSemProc.06111.9},
  annote =	{Keywords: Multiparty communication complexity, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.06111.17
The Cell Probe Complexity of Succinct Data Structures

Authors: Anna Gál and Peter Bro Miltersen

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
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 imes {0,1}^m ightarrow {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 ll 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 ightarrow {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 {em succinct} representations where $s = n + r$ for some {em redundancy} $r ll 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 geq 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 {em systematic} or {em index} structures $phi$ satisfying $phi(x) = x cdot phi^*(x)$ for some map $phi^*$ (where $cdot$ 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.
Cite as

Anna Gál and Peter Bro Miltersen. The Cell Probe Complexity of Succinct Data Structures. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:DagSemProc.06111.17,
  author =	{G\'{a}l, Anna and Miltersen, Peter Bro},
  title =	{{The Cell Probe Complexity of Succinct Data Structures}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.17},
  URN =		{urn:nbn:de:0030-drops-6065},
  doi =		{10.4230/DagSemProc.06111.17},
  annote =	{Keywords: Cell probe model, data structures, lower bounds, time-space tradeoffs}
}

Gál, Anna

Document
DOI: 10.4230/DagRep.13.3.17
Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)

Authors: Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar

Published in: Dagstuhl Reports, Volume 13, Issue 3 (2023)

Abstract
This report documents the program and activities of Dagstuhl Seminar 23111 "Computational Complexity of Discrete Problems", which was held in-person in March 2023 (the previous instance of the seminar series had been held online in March 2021). Following a description of the seminar’s objectives and its overall organization, this report lists the different major talks given during the seminar in alphabetical order of speakers, followed by the abstracts of the talks, including the main references and relevant sources where applicable. The return to an in-person setting allowed an intense atmosphere of active research and interaction throughout the five day seminar.
Cite as

Anna Gál, Meena Mahajan, Rahul Santhanam, Till Tantau, and Manaswi Paraashar. Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111). In Dagstuhl Reports, Volume 13, Issue 3, pp. 17-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.13.3.17,
  author =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 23111)}},
  pages =	{17--31},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{3},
  editor =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till and Paraashar, Manaswi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.3.17},
  URN =		{urn:nbn:de:0030-drops-192261},
  doi =		{10.4230/DagRep.13.3.17},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.32
Certificate Games

Authors: Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
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.
Cite as

Sourav Chakraborty, Anna Gál, Sophie Laplante, Rajat Mittal, and Anupa Sunny. Certificate Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 32:1-32:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{chakraborty_et_al:LIPIcs.ITCS.2023.32,
  author =	{Chakraborty, Sourav and G\'{a}l, Anna and Laplante, Sophie and Mittal, Rajat and Sunny, Anupa},
  title =	{{Certificate Games}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{32:1--32:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.32},
  URN =		{urn:nbn:de:0030-drops-175353},
  doi =		{10.4230/LIPIcs.ITCS.2023.32},
  annote =	{Keywords: block sensitivity, boolean function complexity, certificate complexity, query complexity, sensitivity, zero-communication two-player games}
}
Document
DOI: 10.4230/DagRep.11.2.1
Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)

Authors: Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau

Published in: Dagstuhl Reports, Volume 11, Issue 2 (2021)

Abstract
This report documents the program and activities of Dagstuhl Seminar 21121 "Computational Complexity of Discrete Problems," which was held online in March 2021. Starting with a description of the organization of the online meeting and the topics covered, we then list the different talks given during the seminar in alphabetical order of speakers, followed by the abstracts of the talks, including the main references and relevant sources where applicable. Despite the fact that only a compressed daily time slot was available for the seminar with participants from time zones spanning the whole globe and despite the fact that informal discussions were harder to hold than in a typical on-site seminar, the rate of participation throughout the seminar was very high and many lively scientific debates were held.
Cite as

Anna Gál, Meena Mahajan, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121). In Dagstuhl Reports, Volume 11, Issue 2, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.11.2.1,
  author =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 21121)}},
  pages =	{1--16},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2021},
  volume =	{11},
  number =	{2},
  editor =	{G\'{a}l, Anna and Mahajan, Meena and Santhanam, Rahul and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.2.1},
  URN =		{urn:nbn:de:0030-drops-146836},
  doi =		{10.4230/DagRep.11.2.1},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, lower bounds, randomness}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2021.31
Diameter Versus Certificate Complexity of Boolean Functions

Authors: Siddhesh Chaubal and Anna Gál

Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)

Abstract
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.
Cite as

Siddhesh Chaubal and Anna Gál. Diameter Versus Certificate Complexity of Boolean Functions. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 31:1-31:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{chaubal_et_al:LIPIcs.MFCS.2021.31,
  author =	{Chaubal, Siddhesh and G\'{a}l, Anna},
  title =	{{Diameter Versus Certificate Complexity of Boolean Functions}},
  booktitle =	{46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
  pages =	{31:1--31:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-201-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{202},
  editor =	{Bonchi, Filippo and Puglisi, Simon J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.31},
  URN =		{urn:nbn:de:0030-drops-144713},
  doi =		{10.4230/LIPIcs.MFCS.2021.31},
  annote =	{Keywords: Sensitivity Conjecture, Boolean Functions, Certificate Complexity, Block Sensitivity, Log-rank Conjecture, Alternating Number}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.58
Lower Bounds for (Non-Monotone) Comparator Circuits

Authors: Anna Gál and Robert Robere

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
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.
Cite as

Anna Gál and Robert Robere. Lower Bounds for (Non-Monotone) Comparator Circuits. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.ITCS.2020.58,
  author =	{G\'{a}l, Anna and Robere, Robert},
  title =	{{Lower Bounds for (Non-Monotone) Comparator Circuits}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{58:1--58:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.58},
  URN =		{urn:nbn:de:0030-drops-117431},
  doi =		{10.4230/LIPIcs.ITCS.2020.58},
  annote =	{Keywords: comparator circuits, circuit complexity, Nechiporuk, lower bounds}
}
Document
DOI: 10.4230/DagRep.9.3.64
Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)

Authors: Anna Gál, Rahul Santhanam, and Till Tantau

Published in: Dagstuhl Reports, Volume 9, Issue 3 (2019)

Abstract
The following report archives the presentations and activities of the March 2019 Dagstuhl Seminar 19121 "Computational Complexity of Discrete Problems". Section 1 summarizes the topics and some specific results offered in selected talks during the course of the week. Section 2 provides a table of contents, listing each of the talks given in alphabetical order. Section 3 contains the abstracts, indicating both the main reference and other relevant sources (where applicable) to allow the reader to investigate the topics further.
Cite as

Anna Gál, Rahul Santhanam, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121). In Dagstuhl Reports, Volume 9, Issue 3, pp. 64-82, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.9.3.64,
  author =	{G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 19121)}},
  pages =	{64--82},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{9},
  number =	{3},
  editor =	{G\'{a}l, Anna and Santhanam, Rahul and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.9.3.64},
  URN =		{urn:nbn:de:0030-drops-112920},
  doi =		{10.4230/DagRep.9.3.64},
  annote =	{Keywords: circuit complexity, communication complexity, computational complexity, parametrisation, randomness}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2019.35
Cubic Formula Size Lower Bounds Based on Compositions with Majority

Authors: Anna Gál, Avishay Tal, and Adrian Trejo Nuñez

Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)

Abstract
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.
Cite as

Anna Gál, Avishay Tal, and Adrian Trejo Nuñez. Cubic Formula Size Lower Bounds Based on Compositions with Majority. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 35:1-35:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.ITCS.2019.35,
  author =	{G\'{a}l, Anna and Tal, Avishay and Trejo Nu\~{n}ez, Adrian},
  title =	{{Cubic Formula Size Lower Bounds Based on Compositions with Majority}},
  booktitle =	{10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
  pages =	{35:1--35:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-095-8},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{124},
  editor =	{Blum, Avrim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.35},
  URN =		{urn:nbn:de:0030-drops-101283},
  doi =		{10.4230/LIPIcs.ITCS.2019.35},
  annote =	{Keywords: formula lower bounds, random restrictions, KRW conjecture, composition}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2018.13
New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Authors: Siddhesh Chaubal and Anna Gál

Published in: LIPIcs, Volume 122, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)

Abstract
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.
Cite as

Siddhesh Chaubal and Anna Gál. New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{chaubal_et_al:LIPIcs.FSTTCS.2018.13,
  author =	{Chaubal, Siddhesh and G\'{a}l, Anna},
  title =	{{New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Ganguly, Sumit and Pandya, Paritosh},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2018.13},
  URN =		{urn:nbn:de:0030-drops-99129},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.13},
  annote =	{Keywords: Sensitivity Conjecture, Boolean Functions, Complexity Measures}
}
Document
DOI: 10.4230/DagRep.7.3.45
Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)

Authors: Anna Gál, Michal Koucký, Oded Regev, and Till Tantau

Published in: Dagstuhl Reports, Volume 7, Issue 3 (2017)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 17121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in alphabetical order. The last section contains the abstracts of the talks.
Cite as

Anna Gál, Michal Koucký, Oded Regev, and Till Tantau. Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121). In Dagstuhl Reports, Volume 7, Issue 3, pp. 45-69, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.7.3.45,
  author =	{G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 17121)}},
  pages =	{45--69},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2017},
  volume =	{7},
  number =	{3},
  editor =	{G\'{a}l, Anna and Kouck\'{y}, Michal and Regev, Oded and Tantau, Till},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.7.3.45},
  URN =		{urn:nbn:de:0030-drops-73611},
  doi =		{10.4230/DagRep.7.3.45},
  annote =	{Keywords: Computational Complexity}
}
Document
DOI: 10.4230/DagRep.4.3.62
Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)

Authors: Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk

Published in: Dagstuhl Reports, Volume 4, Issue 3 (2014)

Abstract
This report documents the program and the outcomes of Dagstuhl Seminar 14121 "Computational Complexity of Discrete Problems". The first section gives an overview of the topics covered and the organization of the meeting. Section 2 lists the talks given in chronological order. The last section contains the abstracts of the talks.
Cite as

Anna Gal, Michal Koucky, Oded Regev, and Rüdiger Reischuk. Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121). In Dagstuhl Reports, Volume 4, Issue 3, pp. 62-84, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@Article{gal_et_al:DagRep.4.3.62,
  author =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  title =	{{Computational Complexity of Discrete Problems (Dagstuhl Seminar 14121)}},
  pages =	{62--84},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2014},
  volume =	{4},
  number =	{3},
  editor =	{Gal, Anna and Koucky, Michal and Regev, Oded and Reischuk, R\"{u}diger},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.3.62},
  URN =		{urn:nbn:de:0030-drops-45921},
  doi =		{10.4230/DagRep.4.3.62},
  annote =	{Keywords: discrete problems, computational complexity, Turing machines, Boolean circuits, arithmetic circuits, quantum computing, communication complexity, pseudorandomness, derandomization, approximation, data streams}
}
Document
DOI: 10.4230/LIPIcs.STACS.2011.673
Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length

Authors: Anna Gal and Andrew Mills

Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)

Abstract
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.
Cite as

Anna Gal and Andrew Mills. Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 673-684, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:LIPIcs.STACS.2011.673,
  author =	{Gal, Anna and Mills, Andrew},
  title =	{{Three Query Locally Decodable Codes with Higher Correctness Require Exponential Length}},
  booktitle =	{28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)},
  pages =	{673--684},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-25-5},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{9},
  editor =	{Schwentick, Thomas and D\"{u}rr, Christoph},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.673},
  URN =		{urn:nbn:de:0030-drops-30534},
  doi =		{10.4230/LIPIcs.STACS.2011.673},
  annote =	{Keywords: error correcting codes}
}
Document
DOI: 10.4230/DagSemProc.06111.10
Incremental branching programs

Authors: Anna Gál, Pierre McKenzie, and Michal Koucký

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We propose a new model of restricted branching programs which we call {em incremental branching programs}. We show that {em syntactic} incremental branching programs capture previously studied structured models of computation for the problem GEN, namely marking machines [Cook74]. and Poon's extension [Poon93] of jumping automata on graphs [CookRackoff80]. We then prove exponential size lower bounds for our syntactic incremental model, and for some other restricted branching program models as well. We further show that nondeterministic syntactic incremental branching programs are provably stronger than their deterministic counterpart when solving a natural NL-complete GEN subproblem. It remains open if syntactic incremental branching programs are as powerful as unrestricted branching programs for GEN problems. Joint work with Anna Gál and Michal Koucký
Cite as

Anna Gál, Pierre McKenzie, and Michal Koucký. Incremental branching programs. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:DagSemProc.06111.10,
  author =	{G\'{a}l, Anna and McKenzie, Pierre and Kouck\'{y}, Michal},
  title =	{{Incremental branching programs}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.10},
  URN =		{urn:nbn:de:0030-drops-6230},
  doi =		{10.4230/DagSemProc.06111.10},
  annote =	{Keywords: Complexity theory, branching programs, logarithmic space, marking machines}
}
Document
DOI: 10.4230/DagSemProc.06111.9
Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity

Authors: Jeff Ford and Anna Gál

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
We develop a new method for estimating the discrepancy of tensors associated with multiparty communication problems in the ``Number on the Forehead'' model of Chandra, Furst and Lipton. We define an analogue of the Hadamard property of matrices for tensors in multiple dimensions and show that any $k$-party communication problem represented by a Hadamard tensor must have $Omega(n/2^k)$ multiparty communication complexity. We also exhibit constructions of Hadamard tensors, giving $Omega(n/2^k)$ lower bounds on multiparty communication complexity for a new class of explicitly defined Boolean functions.
Cite as

Jeff Ford and Anna Gál. Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{ford_et_al:DagSemProc.06111.9,
  author =	{Ford, Jeff and G\'{a}l, Anna},
  title =	{{Hadamard Tensors and Lower Bounds on Multiparty Communication Complexity}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--20},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.9},
  URN =		{urn:nbn:de:0030-drops-6076},
  doi =		{10.4230/DagSemProc.06111.9},
  annote =	{Keywords: Multiparty communication complexity, lower bounds}
}
Document
DOI: 10.4230/DagSemProc.06111.17
The Cell Probe Complexity of Succinct Data Structures

Authors: Anna Gál and Peter Bro Miltersen

Published in: Dagstuhl Seminar Proceedings, Volume 6111, Complexity of Boolean Functions (2006)

Abstract
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 imes {0,1}^m ightarrow {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 ll 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 ightarrow {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 {em succinct} representations where $s = n + r$ for some {em redundancy} $r ll 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 geq 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 {em systematic} or {em index} structures $phi$ satisfying $phi(x) = x cdot phi^*(x)$ for some map $phi^*$ (where $cdot$ 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.
Cite as

Anna Gál and Peter Bro Miltersen. The Cell Probe Complexity of Succinct Data Structures. In Complexity of Boolean Functions. Dagstuhl Seminar Proceedings, Volume 6111, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{gal_et_al:DagSemProc.06111.17,
  author =	{G\'{a}l, Anna and Miltersen, Peter Bro},
  title =	{{The Cell Probe Complexity of Succinct Data Structures}},
  booktitle =	{Complexity of Boolean Functions},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{6111},
  editor =	{Matthias Krause and Pavel Pudl\'{a}k and R\"{u}diger Reischuk and Dieter van Melkebeek},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06111.17},
  URN =		{urn:nbn:de:0030-drops-6065},
  doi =		{10.4230/DagSemProc.06111.17},
  annote =	{Keywords: Cell probe model, data structures, lower bounds, time-space tradeoffs}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact