Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Harm Derksen, Peter Ivanov, Chin Ho Lee, and Emanuele Viola. Pseudorandomness, Symmetry, Smoothing: I. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 18:1-18:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{derksen_et_al:LIPIcs.CCC.2024.18, author = {Derksen, Harm and Ivanov, Peter and Lee, Chin Ho and Viola, Emanuele}, title = {{Pseudorandomness, Symmetry, Smoothing: I}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {18:1--18:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.18}, URN = {urn:nbn:de:0030-drops-204144}, doi = {10.4230/LIPIcs.CCC.2024.18}, annote = {Keywords: pseudorandomness, k-wise uniform distributions, small-bias distributions, noise, symmetric tests, thresholds, Krawtchouk polynomials} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez, and Carlos Palazuelos. Learning Low-Degree Quantum Objects. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{arunachalam_et_al:LIPIcs.ICALP.2024.13, author = {Arunachalam, Srinivasan and Dutt, Arkopal and Escudero Guti\'{e}rrez, Francisco and Palazuelos, Carlos}, title = {{Learning Low-Degree Quantum Objects}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.13}, URN = {urn:nbn:de:0030-drops-201563}, doi = {10.4230/LIPIcs.ICALP.2024.13}, annote = {Keywords: Tomography} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Ari Karchmer. Distributional PAC-Learning from Nisan’s Natural Proofs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 68:1-68:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{karchmer:LIPIcs.ITCS.2024.68, author = {Karchmer, Ari}, title = {{Distributional PAC-Learning from Nisan’s Natural Proofs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {68:1--68:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.68}, URN = {urn:nbn:de:0030-drops-195964}, doi = {10.4230/LIPIcs.ITCS.2024.68}, annote = {Keywords: PAC-learning, average-case complexity, communication complexity, natural proofs} }
Published in: LIPIcs, Volume 266, 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)
Mark Bun and Nadezhda Voronova. Approximate Degree Lower Bounds for Oracle Identification Problems. In 18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 266, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bun_et_al:LIPIcs.TQC.2023.1, author = {Bun, Mark and Voronova, Nadezhda}, title = {{Approximate Degree Lower Bounds for Oracle Identification Problems}}, booktitle = {18th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2023)}, pages = {1:1--1:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-283-9}, ISSN = {1868-8969}, year = {2023}, volume = {266}, editor = {Fawzi, Omar and Walter, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2023.1}, URN = {urn:nbn:de:0030-drops-183113}, doi = {10.4230/LIPIcs.TQC.2023.1}, annote = {Keywords: Approximate degree, quantum query complexity, communication complexity, ordered search, polynomial approximations, polynomial method} }
Published in: LIPIcs, Volume 237, 13th International Conference on Interactive Theorem Proving (ITP 2022)
Alley Stoughton, Carol Chen, Marco Gaboardi, and Weihao Qu. Formalizing Algorithmic Bounds in the Query Model in EasyCrypt. In 13th International Conference on Interactive Theorem Proving (ITP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 237, pp. 30:1-30:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{stoughton_et_al:LIPIcs.ITP.2022.30, author = {Stoughton, Alley and Chen, Carol and Gaboardi, Marco and Qu, Weihao}, title = {{Formalizing Algorithmic Bounds in the Query Model in EasyCrypt}}, booktitle = {13th International Conference on Interactive Theorem Proving (ITP 2022)}, pages = {30:1--30:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-252-5}, ISSN = {1868-8969}, year = {2022}, volume = {237}, editor = {Andronick, June and de Moura, Leonardo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2022.30}, URN = {urn:nbn:de:0030-drops-167399}, doi = {10.4230/LIPIcs.ITP.2022.30}, annote = {Keywords: query model, lower bound, upper bound, adversary argument, EasyCrypt} }
Published in: LIPIcs, Volume 218, 3rd Symposium on Foundations of Responsible Computing (FORC 2022)
Mark Bun, Jörg Drechsler, Marco Gaboardi, Audra McMillan, and Jayshree Sarathy. Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling. In 3rd Symposium on Foundations of Responsible Computing (FORC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 218, pp. 1:1-1:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{bun_et_al:LIPIcs.FORC.2022.1, author = {Bun, Mark and Drechsler, J\"{o}rg and Gaboardi, Marco and McMillan, Audra and Sarathy, Jayshree}, title = {{Controlling Privacy Loss in Sampling Schemes: An Analysis of Stratified and Cluster Sampling}}, booktitle = {3rd Symposium on Foundations of Responsible Computing (FORC 2022)}, pages = {1:1--1:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-226-6}, ISSN = {1868-8969}, year = {2022}, volume = {218}, editor = {Celis, L. Elisa}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FORC.2022.1}, URN = {urn:nbn:de:0030-drops-165243}, doi = {10.4230/LIPIcs.FORC.2022.1}, annote = {Keywords: privacy, differential privacy, survey design, survey sampling} }
Published in: LIPIcs, Volume 158, 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)
Nikhil S. Mande, Justin Thaler, and Shuchen Zhu. Improved Approximate Degree Bounds for k-Distinctness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 158, pp. 2:1-2:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{mande_et_al:LIPIcs.TQC.2020.2, author = {Mande, Nikhil S. and Thaler, Justin and Zhu, Shuchen}, title = {{Improved Approximate Degree Bounds for k-Distinctness}}, booktitle = {15th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2020)}, pages = {2:1--2:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-146-7}, ISSN = {1868-8969}, year = {2020}, volume = {158}, editor = {Flammia, Steven T.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TQC.2020.2}, URN = {urn:nbn:de:0030-drops-120613}, doi = {10.4230/LIPIcs.TQC.2020.2}, annote = {Keywords: Quantum Query Complexity, Approximate Degree, Dual Polynomials, k-distinctness} }
Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)
Haim Kaplan, Micha Sharir, and Uri Stemmer. How to Find a Point in the Convex Hull Privately. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{kaplan_et_al:LIPIcs.SoCG.2020.52, author = {Kaplan, Haim and Sharir, Micha and Stemmer, Uri}, title = {{How to Find a Point in the Convex Hull Privately}}, booktitle = {36th International Symposium on Computational Geometry (SoCG 2020)}, pages = {52:1--52:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-143-6}, ISSN = {1868-8969}, year = {2020}, volume = {164}, editor = {Cabello, Sergio and Chen, Danny Z.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.52}, URN = {urn:nbn:de:0030-drops-122107}, doi = {10.4230/LIPIcs.SoCG.2020.52}, annote = {Keywords: Differential privacy, Tukey depth, Convex hull} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Mark Bun and Justin Thaler. The Large-Error Approximate Degree of AC^0. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2019.55, author = {Bun, Mark and Thaler, Justin}, title = {{The Large-Error Approximate Degree of AC^0}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {55:1--55:16}, 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.55}, URN = {urn:nbn:de:0030-drops-112709}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.55}, annote = {Keywords: approximate degree, discrepancy, margin complexity, polynomial approximations, secret sharing, threshold circuits} }
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} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Mark Bun, Nikhil S. Mande, and Justin Thaler. Sign-Rank Can Increase Under Intersection. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bun_et_al:LIPIcs.ICALP.2019.30, author = {Bun, Mark and Mande, Nikhil S. and Thaler, Justin}, title = {{Sign-Rank Can Increase Under Intersection}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.30}, URN = {urn:nbn:de:0030-drops-106067}, doi = {10.4230/LIPIcs.ICALP.2019.30}, annote = {Keywords: Sign rank, dimension complexity, communication complexity, learning theory} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Mark Bun and Justin Thaler. Approximate Degree and the Complexity of Depth Three Circuits. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 35:1-35:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2018.35, author = {Bun, Mark and Thaler, Justin}, title = {{Approximate Degree and the Complexity of Depth Three Circuits}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {35:1--35:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.35}, URN = {urn:nbn:de:0030-drops-94390}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.35}, annote = {Keywords: approximate degree, communication complexity, learning theory, polynomial approximation, threshold circuits} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Mark Bun and Justin Thaler. Improved Bounds on the Sign-Rank of AC^0. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 37:1-37:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bun_et_al:LIPIcs.ICALP.2016.37, author = {Bun, Mark and Thaler, Justin}, title = {{Improved Bounds on the Sign-Rank of AC^0}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {37:1--37:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.37}, URN = {urn:nbn:de:0030-drops-63173}, doi = {10.4230/LIPIcs.ICALP.2016.37}, annote = {Keywords: Sign-rank, circuit complexity, communication complexity, constant-depth circuits} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Mark Bun and Thomas Steinke. Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 625-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2015.625, author = {Bun, Mark and Steinke, Thomas}, title = {{Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {625--644}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.625}, URN = {urn:nbn:de:0030-drops-53274}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.625}, annote = {Keywords: Polynomial Approximations, Pseudorandomness, Concentration, Learning Theory, Halfspaces} }