Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Eshan Chattopadhyay, Jesse Goodman, and Mohit Gurumukhani. Extractors for Polynomial Sources over 𝔽₂. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 28:1-28:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2024.28, author = {Chattopadhyay, Eshan and Goodman, Jesse and Gurumukhani, Mohit}, title = {{Extractors for Polynomial Sources over \mathbb{F}₂}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {28:1--28:24}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.28}, URN = {urn:nbn:de:0030-drops-195569}, doi = {10.4230/LIPIcs.ITCS.2024.28}, annote = {Keywords: Extractors, low-degree polynomials, varieties, sumset extractors} }
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-dev.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)
Eshan Chattopadhyay and Jyun-Jie Liao. Hardness Against Linear Branching Programs and More. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 9:1-9:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2023.9, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Hardness Against Linear Branching Programs and More}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {9:1--9:27}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.9}, URN = {urn:nbn:de:0030-drops-182794}, doi = {10.4230/LIPIcs.CCC.2023.9}, annote = {Keywords: linear branching programs, circuit lower bound, sumset extractors, hitting sets} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Omar Alrabiah, Eshan Chattopadhyay, Jesse Goodman, Xin Li, and João Ribeiro. Low-Degree Polynomials Extract From Local Sources. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 10:1-10:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{alrabiah_et_al:LIPIcs.ICALP.2022.10, author = {Alrabiah, Omar and Chattopadhyay, Eshan and Goodman, Jesse and Li, Xin and Ribeiro, Jo\~{a}o}, title = {{Low-Degree Polynomials Extract From Local Sources}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.10}, URN = {urn:nbn:de:0030-drops-163519}, doi = {10.4230/LIPIcs.ICALP.2022.10}, annote = {Keywords: Randomness extractors, local sources, samplable sources, AC⁰ circuits, branching programs, low-degree polynomials, Chevalley-Warning} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Eshan Chattopadhyay, Jesse Goodman, and David Zuckerman. The Space Complexity of Sampling. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 40:1-40:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2022.40, author = {Chattopadhyay, Eshan and Goodman, Jesse and Zuckerman, David}, title = {{The Space Complexity of Sampling}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {40:1--40:23}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.40}, URN = {urn:nbn:de:0030-drops-156366}, doi = {10.4230/LIPIcs.ITCS.2022.40}, annote = {Keywords: Complexity of distributions, complexity of sampling, extractors, list decodable codes, lower bounds, read-once branching programs, small-space computation} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Uma Girish, Ran Raz, and Wei Zhan. Lower Bounds for XOR of Forrelations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 52:1-52:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{girish_et_al:LIPIcs.APPROX/RANDOM.2021.52, author = {Girish, Uma and Raz, Ran and Zhan, Wei}, title = {{Lower Bounds for XOR of Forrelations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {52:1--52:14}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.52}, URN = {urn:nbn:de:0030-drops-147453}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.52}, annote = {Keywords: Forrelation, Quasipolynomial, Separation, Quantum versus Classical, Xor} }
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-dev.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-dev.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 200, 36th Computational Complexity Conference (CCC 2021)
Oded Goldreich and Avi Wigderson. Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 12:1-12:74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldreich_et_al:LIPIcs.CCC.2021.12, author = {Goldreich, Oded and Wigderson, Avi}, title = {{Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {12:1--12:74}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.12}, URN = {urn:nbn:de:0030-drops-142867}, doi = {10.4230/LIPIcs.CCC.2021.12}, annote = {Keywords: Asymmetric graphs, expanders, testing graph properties, two-source extractors, non-malleable extractors, coding theory, tolerant testing, random graphs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.CCC.2021.22, author = {Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and Ta-Shma, Amnon}, title = {{Error Reduction for Weighted PRGs Against Read Once Branching Programs}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {22:1--22:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.22}, URN = {urn:nbn:de:0030-drops-142963}, doi = {10.4230/LIPIcs.CCC.2021.22}, annote = {Keywords: Pseudorandom generators, Read once branching programs, Space-bounded computation} }
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-dev.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 169, 35th Computational Complexity Conference (CCC 2020)
Eshan Chattopadhyay and Jyun-Jie Liao. Optimal Error Pseudodistributions for Read-Once Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 25:1-25:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2020.25, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Optimal Error Pseudodistributions for Read-Once Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {25:1--25:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.25}, URN = {urn:nbn:de:0030-drops-125779}, doi = {10.4230/LIPIcs.CCC.2020.25}, annote = {Keywords: Derandomization, explicit constructions, space-bounded computation} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Eshan Chattopadhyay, Anindya De, and Rocco A. Servedio. Simple and Efficient Pseudorandom Generators from Gaussian Processes. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 4:1-4:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2019.4, author = {Chattopadhyay, Eshan and De, Anindya and Servedio, Rocco A.}, title = {{Simple and Efficient Pseudorandom Generators from Gaussian Processes}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {4:1--4:33}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.4}, URN = {urn:nbn:de:0030-drops-108262}, doi = {10.4230/LIPIcs.CCC.2019.4}, annote = {Keywords: Polynomial threshold functions, Gaussian processes, Johnson-Lindenstrauss, pseudorandom generators} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.ITCS.2019.22, author = {Chattopadhyay, Eshan and Hatami, Pooya and Lovett, Shachar and Tal, Avishay}, title = {{Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {22:1--22:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.22}, URN = {urn:nbn:de:0030-drops-101150}, doi = {10.4230/LIPIcs.ITCS.2019.22}, annote = {Keywords: Derandomization, Pseudorandom generator, Explicit construction, Random walk, Small-depth circuits with parity gates} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Eshan Chattopadhyay, Pooya Hatami, Kaave Hosseini, and Shachar Lovett. Pseudorandom Generators from Polarizing Random Walks. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 1:1-1:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2018.1, author = {Chattopadhyay, Eshan and Hatami, Pooya and Hosseini, Kaave and Lovett, Shachar}, title = {{Pseudorandom Generators from Polarizing Random Walks}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {1:1--1:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.1}, URN = {urn:nbn:de:0030-drops-88880}, doi = {10.4230/LIPIcs.CCC.2018.1}, annote = {Keywords: AC0, branching program, polarization, pseudorandom generators, random walks, Sensitivity} }
Feedback for Dagstuhl Publishing