Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Yuval Filmus, Itai Leigh, Artur Riazanov, and Dmitry Sokolov. Sampling and Certifying Symmetric Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 36:1-36:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{filmus_et_al:LIPIcs.APPROX/RANDOM.2023.36, author = {Filmus, Yuval and Leigh, Itai and Riazanov, Artur and Sokolov, Dmitry}, title = {{Sampling and Certifying Symmetric Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {36:1--36:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.36}, URN = {urn:nbn:de:0030-drops-188611}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.36}, annote = {Keywords: sampling, lower bounds, robust sunflowers, decision trees, switching networks} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Peter Ivanov, Liam Pavlovic, and Emanuele Viola. On Correlation Bounds Against Polynomials. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 3:1-3:35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{ivanov_et_al:LIPIcs.CCC.2023.3, author = {Ivanov, Peter and Pavlovic, Liam and Viola, Emanuele}, title = {{On Correlation Bounds Against Polynomials}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {3:1--3:35}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.3}, URN = {urn:nbn:de:0030-drops-182734}, doi = {10.4230/LIPIcs.CCC.2023.3}, annote = {Keywords: Correlation bounds, Polynomials} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Emanuele Viola. New Sampling Lower Bounds via the Separator. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 26:1-26:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{viola:LIPIcs.CCC.2023.26, author = {Viola, Emanuele}, title = {{New Sampling Lower Bounds via the Separator}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {26:1--26:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.26}, URN = {urn:nbn:de:0030-drops-182967}, doi = {10.4230/LIPIcs.CCC.2023.26}, annote = {Keywords: Sampling, data structures, lower bounds, cell probe, decision forest, AC0, rank, predecessor} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Xuangui Huang, Peter Ivanov, and Emanuele Viola. Affine Extractors and AC0-Parity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2022.9, author = {Huang, Xuangui and Ivanov, Peter and Viola, Emanuele}, title = {{Affine Extractors and AC0-Parity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.9}, URN = {urn:nbn:de:0030-drops-171313}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.9}, annote = {Keywords: affine extractor, resilient function, constant-depth circuit, parity gate, inner product} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, and Akshayaram Srinivasan. Bounded Indistinguishability for Simple Sources. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 26:1-26:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{bogdanov_et_al:LIPIcs.ITCS.2022.26, author = {Bogdanov, Andrej and Dinesh, Krishnamoorthy and Filmus, Yuval and Ishai, Yuval and Kaplan, Avi and Srinivasan, Akshayaram}, title = {{Bounded Indistinguishability for Simple Sources}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {26:1--26:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.26}, URN = {urn:nbn:de:0030-drops-156223}, doi = {10.4230/LIPIcs.ITCS.2022.26}, annote = {Keywords: Pseudorandomness, bounded indistinguishability, complexity of sampling, constant-depth circuits, secret sharing, leakage-resilient cryptography} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
W. T. Gowers and Emanuele Viola. Mixing in Non-Quasirandom Groups. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 80:1-80:9, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{gowers_et_al:LIPIcs.ITCS.2022.80, author = {Gowers, W. T. and Viola, Emanuele}, title = {{Mixing in Non-Quasirandom Groups}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {80:1--80:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.80}, URN = {urn:nbn:de:0030-drops-156761}, doi = {10.4230/LIPIcs.ITCS.2022.80}, annote = {Keywords: Groups, representation theory, mixing, communication complexity, quasi-random} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Ronen Shaltiel and Emanuele Viola. On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 116:1-116:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{shaltiel_et_al:LIPIcs.ITCS.2022.116, author = {Shaltiel, Ronen and Viola, Emanuele}, title = {{On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {116:1--116:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.116}, URN = {urn:nbn:de:0030-drops-157122}, doi = {10.4230/LIPIcs.ITCS.2022.116}, annote = {Keywords: Complexity Theory, Derandomization, Pseudorandom generators, Black-box proofs} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Jarosław Błasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, and Emanuele Viola. Fourier Growth of Structured 𝔽₂-Polynomials and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 53:1-53:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{blasiok_et_al:LIPIcs.APPROX/RANDOM.2021.53, author = {B{\l}asiok, Jaros{\l}aw and Ivanov, Peter and Jin, Yaonan and Lee, Chin Ho and Servedio, Rocco A. and Viola, Emanuele}, title = {{Fourier Growth of Structured \mathbb{F}₂-Polynomials and Applications}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-147462}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.53}, annote = {Keywords: Fourier analysis, Pseudorandomness, Fourier growth} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Eshan Chattopadhyay, Jason Gaitonde, Chin Ho Lee, Shachar Lovett, and Abhishek Shetty. Fractional Pseudorandom Generators from Any Fourier Level. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 10:1-10:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2021.10, author = {Chattopadhyay, Eshan and Gaitonde, Jason and Lee, Chin Ho and Lovett, Shachar and Shetty, Abhishek}, title = {{Fractional Pseudorandom Generators from Any Fourier Level}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {10:1--10:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.10}, URN = {urn:nbn:de:0030-drops-142843}, doi = {10.4230/LIPIcs.CCC.2021.10}, annote = {Keywords: Derandomization, pseudorandomness, pseudorandom generators, Fourier analysis} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Emanuele Viola. Fourier Conjectures, Correlation Bounds, and Majority. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 111:1-111:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{viola:LIPIcs.ICALP.2021.111, author = {Viola, Emanuele}, title = {{Fourier Conjectures, Correlation Bounds, and Majority}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {111:1--111:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.111}, URN = {urn:nbn:de:0030-drops-141806}, doi = {10.4230/LIPIcs.ICALP.2021.111}, annote = {Keywords: Fourier analysis, polynomials, Majority, correlation, lower bound, conjectures} }
Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)
Mahdi Cheraghchi, Shuichi Hirahara, Dimitrios Myrisiotis, and Yuichi Yoshida. One-Tape Turing Machine and Branching Program Lower Bounds for MCSP. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 23:1-23:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheraghchi_et_al:LIPIcs.STACS.2021.23, author = {Cheraghchi, Mahdi and Hirahara, Shuichi and Myrisiotis, Dimitrios and Yoshida, Yuichi}, title = {{One-Tape Turing Machine and Branching Program Lower Bounds for MCSP}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.23}, URN = {urn:nbn:de:0030-drops-136681}, doi = {10.4230/LIPIcs.STACS.2021.23}, annote = {Keywords: Minimum Circuit Size Problem, Kolmogorov Complexity, One-Tape Turing Machines, Branching Programs, Lower Bounds, Pseudorandom Generators, Hitting Set Generators} }
Published in: LIPIcs, Volume 181, 31st International Symposium on Algorithms and Computation (ISAAC 2020)
Xuangui Huang. Space Hardness of Solving Structured Linear Systems. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 56:1-56:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{huang:LIPIcs.ISAAC.2020.56, author = {Huang, Xuangui}, title = {{Space Hardness of Solving Structured Linear Systems}}, booktitle = {31st International Symposium on Algorithms and Computation (ISAAC 2020)}, pages = {56:1--56:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-173-3}, ISSN = {1868-8969}, year = {2020}, volume = {181}, editor = {Cao, Yixin and Cheng, Siu-Wing and Li, Minming}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2020.56}, URN = {urn:nbn:de:0030-drops-134001}, doi = {10.4230/LIPIcs.ISAAC.2020.56}, annote = {Keywords: linear system solver, logarithmic space, threshold circuit} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Joshua Cook. Size Bounds on Low Depth Circuits for Promise Majority. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 19:1-19:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cook:LIPIcs.FSTTCS.2020.19, author = {Cook, Joshua}, title = {{Size Bounds on Low Depth Circuits for Promise Majority}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.19}, URN = {urn:nbn:de:0030-drops-132609}, doi = {10.4230/LIPIcs.FSTTCS.2020.19}, annote = {Keywords: AC0, Approximate Counting, Approximate Majority, Promise Majority, Depth 3 Circuits, Circuit Lower Bound} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Ronen Shaltiel. Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{shaltiel:LIPIcs.APPROX/RANDOM.2020.10, author = {Shaltiel, Ronen}, title = {{Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.10}, URN = {urn:nbn:de:0030-drops-126138}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.10}, annote = {Keywords: Yao’s XOR lemma, Hardness amplification, black-box reductions} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler, and Christopher Williamson. Approximate Degree, Secret Sharing, and Concentration Phenomena. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 71:1-71:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bogdanov_et_al:LIPIcs.APPROX-RANDOM.2019.71, author = {Bogdanov, Andrej and Mande, Nikhil S. and Thaler, Justin and Williamson, Christopher}, title = {{Approximate Degree, Secret Sharing, and Concentration Phenomena}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {71:1--71:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.71}, URN = {urn:nbn:de:0030-drops-112869}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.71}, annote = {Keywords: approximate degree, dual polynomial, pseudorandomness, polynomial approximation, secret sharing} }
Feedback for Dagstuhl Publishing