Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Eshan Chattopadhyay and Jyun-Jie Liao. Recursive Error Reduction for Regular Branching Programs. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 29:1-29:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2024.29, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Recursive Error Reduction for Regular Branching Programs}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {29:1--29:20}, 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.29}, URN = {urn:nbn:de:0030-drops-195571}, doi = {10.4230/LIPIcs.ITCS.2024.29}, annote = {Keywords: read-once branching program, regular branching program, weighted pseudorandom generator, derandomization} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Vinayak M. Kumar. Tight Correlation Bounds for Circuits Between AC0 and TC0. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 18:1-18:40, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kumar:LIPIcs.CCC.2023.18, author = {Kumar, Vinayak M.}, title = {{Tight Correlation Bounds for Circuits Between AC0 and TC0}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {18:1--18:40}, 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.18}, URN = {urn:nbn:de:0030-drops-182885}, doi = {10.4230/LIPIcs.CCC.2023.18}, annote = {Keywords: AC⁰, TC⁰, Switching Lemma, Lower Bounds, Correlation Bounds, Circuit Complexity} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Lijie Chen, Xin Lyu, Avishay Tal, and Hongxun Wu. New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 39:1-39:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ICALP.2023.39, author = {Chen, Lijie and Lyu, Xin and Tal, Avishay and Wu, Hongxun}, title = {{New PRGs for Unbounded-Width/Adaptive-Order Read-Once Branching Programs}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {39:1--39:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.39}, URN = {urn:nbn:de:0030-drops-180916}, doi = {10.4230/LIPIcs.ICALP.2023.39}, annote = {Keywords: pseudorandom generators, derandomization, read-once branching programs} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, and Kewen Wu. On Differentially Private Counting on Trees. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 66:1-66:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{ghazi_et_al:LIPIcs.ICALP.2023.66, author = {Ghazi, Badih and Kamath, Pritish and Kumar, Ravi and Manurangsi, Pasin and Wu, Kewen}, title = {{On Differentially Private Counting on Trees}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {66:1--66:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.66}, URN = {urn:nbn:de:0030-drops-181186}, doi = {10.4230/LIPIcs.ICALP.2023.66}, annote = {Keywords: Differential Privacy, Algorithms, Trees, Hierarchies} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlós, and Uri Stemmer. Generalized Private Selection and Testing with High Confidence. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 39:1-39:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.ITCS.2023.39, author = {Cohen, Edith and Lyu, Xin and Nelson, Jelani and Sarl\'{o}s, Tam\'{a}s and Stemmer, Uri}, title = {{Generalized Private Selection and Testing with High Confidence}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {39:1--39:23}, 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.39}, URN = {urn:nbn:de:0030-drops-175426}, doi = {10.4230/LIPIcs.ITCS.2023.39}, annote = {Keywords: differential privacy, sparse vector technique, adaptive data analysis} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Venkatesan Guruswami, Xin Lyu, and Xiuhan Wang. Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{guruswami_et_al:LIPIcs.APPROX/RANDOM.2022.20, author = {Guruswami, Venkatesan and Lyu, Xin and Wang, Xiuhan}, title = {{Range Avoidance for Low-Depth Circuits and Connections to Pseudorandomness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {20:1--20:21}, 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.20}, URN = {urn:nbn:de:0030-drops-171428}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.20}, annote = {Keywords: Pseudorandomness, Explicit constructions, Low-depth circuits, Boolean function analysis, Hitting sets} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Xin Lyu. Improved Pseudorandom Generators for AC⁰ Circuits. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 34:1-34:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{lyu:LIPIcs.CCC.2022.34, author = {Lyu, Xin}, title = {{Improved Pseudorandom Generators for AC⁰ Circuits}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {34:1--34:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.34}, URN = {urn:nbn:de:0030-drops-165963}, doi = {10.4230/LIPIcs.CCC.2022.34}, annote = {Keywords: pseudorandom generators, derandomization, switching Lemmas, AC⁰} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Lijie Chen, Zhenjian Lu, Xin Lyu, and Igor C. Oliveira. Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 51:1-51:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{chen_et_al:LIPIcs.ICALP.2021.51, author = {Chen, Lijie and Lu, Zhenjian and Lyu, Xin and Oliveira, Igor C.}, title = {{Majority vs. Approximate Linear Sum and Average-Case Complexity Below NC¹}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {51:1--51:20}, 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.51}, URN = {urn:nbn:de:0030-drops-141202}, doi = {10.4230/LIPIcs.ICALP.2021.51}, annote = {Keywords: circuit complexity, average-case hardness, complexity lower bounds} }
Feedback for Dagstuhl Publishing