Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Srikanth Srinivasan and S. Venkitesh. On the Probabilistic Degree of an n-Variate Boolean Function. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 42:1-42:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{srinivasan_et_al:LIPIcs.APPROX/RANDOM.2021.42, author = {Srinivasan, Srikanth and Venkitesh, S.}, title = {{On the Probabilistic Degree of an n-Variate Boolean Function}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {42:1--42:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.42}, URN = {urn:nbn:de:0030-drops-147356}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.42}, annote = {Keywords: truly n-variate, Boolean function, probabilistic polynomial, probabilistic degree} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Nutan Limaye, Srikanth Srinivasan, and Utkarsh Tripathi. More on AC^0[oplus] and Variants of the Majority Function. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 22:1-22:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{limaye_et_al:LIPIcs.FSTTCS.2019.22, author = {Limaye, Nutan and Srinivasan, Srikanth and Tripathi, Utkarsh}, title = {{More on AC^0\lbrackoplus\rbrack and Variants of the Majority Function}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {22:1--22:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.22}, URN = {urn:nbn:de:0030-drops-115844}, doi = {10.4230/LIPIcs.FSTTCS.2019.22}, annote = {Keywords: AC^0\lbrackoplus\rbrack, Coin Problem, Promise Majority} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh. On the Probabilistic Degrees of Symmetric Boolean Functions. In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, pp. 28:1-28:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{srinivasan_et_al:LIPIcs.FSTTCS.2019.28, author = {Srinivasan, Srikanth and Tripathi, Utkarsh and Venkitesh, S.}, title = {{On the Probabilistic Degrees of Symmetric Boolean Functions}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {28:1--28:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.28}, URN = {urn:nbn:de:0030-drops-115908}, doi = {10.4230/LIPIcs.FSTTCS.2019.28}, annote = {Keywords: Symmetric Boolean function, probabilistic degree} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Igor Carboni Oliveira, Rahul Santhanam, and Srikanth Srinivasan. Parity Helps to Compute Majority. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{oliveira_et_al:LIPIcs.CCC.2019.23, author = {Oliveira, Igor Carboni and Santhanam, Rahul and Srinivasan, Srikanth}, title = {{Parity Helps to Compute Majority}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {23:1--23:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.23}, URN = {urn:nbn:de:0030-drops-108453}, doi = {10.4230/LIPIcs.CCC.2019.23}, annote = {Keywords: Computational Complexity, Boolean Circuits, Lower Bounds, Parity, Majority} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Chin Ho Lee. Fourier Bounds and Pseudorandom Generators for Product Tests. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 7:1-7:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lee:LIPIcs.CCC.2019.7, author = {Lee, Chin Ho}, title = {{Fourier Bounds and Pseudorandom Generators for Product Tests}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {7:1--7:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.7}, URN = {urn:nbn:de:0030-drops-108296}, doi = {10.4230/LIPIcs.CCC.2019.7}, annote = {Keywords: bounded independence plus noise, Fourier spectrum, product test, pseudorandom generators} }
Feedback for Dagstuhl Publishing