Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Gil Cohen and Itay Cohen. Spectral Expanding Expanders. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 8:1-8:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{cohen_et_al:LIPIcs.CCC.2023.8, author = {Cohen, Gil and Cohen, Itay}, title = {{Spectral Expanding Expanders}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {8:1--8:19}, 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.8}, URN = {urn:nbn:de:0030-drops-182780}, doi = {10.4230/LIPIcs.CCC.2023.8}, annote = {Keywords: Expanders, Normalized Random Walk, Spectral Analysis} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Gil Cohen, Dor Minzer, Shir Peleg, Aaron Potechin, and Amnon Ta-Shma. Expander Random Walks: The General Case and Limitations. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 43:1-43:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.43, author = {Cohen, Gil and Minzer, Dor and Peleg, Shir and Potechin, Aaron and Ta-Shma, Amnon}, title = {{Expander Random Walks: The General Case and Limitations}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {43:1--43:18}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.43}, URN = {urn:nbn:de:0030-drops-163849}, doi = {10.4230/LIPIcs.ICALP.2022.43}, annote = {Keywords: Expander Graphs, Random Walks, Lower Bounds} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Gil Cohen and Tal Yankovitz. LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 44:1-44:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{cohen_et_al:LIPIcs.ICALP.2022.44, author = {Cohen, Gil and Yankovitz, Tal}, title = {{LCC and LDC: Tailor-Made Distance Amplification and a Refined Separation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {44:1--44: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.44}, URN = {urn:nbn:de:0030-drops-163858}, doi = {10.4230/LIPIcs.ICALP.2022.44}, annote = {Keywords: Locally Correctable Codes, Locally Decodable Codes, Distance Amplifications} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Inbar Ben Yaacov, Gil Cohen, and Anand Kumar Narayanan. Candidate Tree Codes via Pascal Determinant Cubes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 54:1-54:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{benyaacov_et_al:LIPIcs.APPROX/RANDOM.2021.54, author = {Ben Yaacov, Inbar and Cohen, Gil and Narayanan, Anand Kumar}, title = {{Candidate Tree Codes via Pascal Determinant Cubes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {54:1--54:22}, 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.54}, URN = {urn:nbn:de:0030-drops-147474}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.54}, annote = {Keywords: Tree codes, Sparse polynomials, Explicit constructions} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Gil Cohen and Tal Yankovitz. Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 1:1-1:57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.CCC.2021.1, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Rate Amplification and Query-Efficient Distance Amplification for Linear LCC and LDC}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {1:1--1:57}, 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.1}, URN = {urn:nbn:de:0030-drops-142750}, doi = {10.4230/LIPIcs.CCC.2021.1}, annote = {Keywords: Locally decodable codes, Locally correctable codes} }
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.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 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Venkatesan Guruswami and Vinayak M. Kumar. Pseudobinomiality of the Sticky Random Walk. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 48:1-48:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{guruswami_et_al:LIPIcs.ITCS.2021.48, author = {Guruswami, Venkatesan and Kumar, Vinayak M.}, title = {{Pseudobinomiality of the Sticky Random Walk}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {48:1--48:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.48}, URN = {urn:nbn:de:0030-drops-135870}, doi = {10.4230/LIPIcs.ITCS.2021.48}, annote = {Keywords: Expander Graphs, Fourier analysis, Markov Chains, Pseudorandomness, Random Walks} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Gil Cohen and Shahar Samocha. Palette-Alternating Tree Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 11:1-11:29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{cohen_et_al:LIPIcs.CCC.2020.11, author = {Cohen, Gil and Samocha, Shahar}, title = {{Palette-Alternating Tree Codes}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {11:1--11:29}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.11}, URN = {urn:nbn:de:0030-drops-125632}, doi = {10.4230/LIPIcs.CCC.2020.11}, annote = {Keywords: Tree Codes, Coding Theory, Interactive Coding Scheme} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Yael Hitron, Merav Parter, and Gur Perri. The Computational Cost of Asynchronous Neural Communication. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 48:1-48:47, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{hitron_et_al:LIPIcs.ITCS.2020.48, author = {Hitron, Yael and Parter, Merav and Perri, Gur}, title = {{The Computational Cost of Asynchronous Neural Communication}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {48:1--48:47}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.48}, URN = {urn:nbn:de:0030-drops-117330}, doi = {10.4230/LIPIcs.ITCS.2020.48}, annote = {Keywords: asynchronous communication, asynchronous computation, spiking neurons, synchronizers} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{benaroya_et_al:LIPIcs.APPROX-RANDOM.2019.43, author = {Ben-Aroya, Avraham and Cohen, Gil and Doron, Dean and Ta-Shma, Amnon}, title = {{Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {43:1--43:20}, 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.43}, URN = {urn:nbn:de:0030-drops-112587}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.43}, annote = {Keywords: Condensers, Extractors, Resilient functions, Explicit constructions} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Xin Li. Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 28:1-28:49, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{li:LIPIcs.CCC.2019.28, author = {Li, Xin}, title = {{Non-Malleable Extractors and Non-Malleable Codes: Partially Optimal Constructions}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {28:1--28:49}, 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.28}, URN = {urn:nbn:de:0030-drops-108507}, doi = {10.4230/LIPIcs.CCC.2019.28}, annote = {Keywords: extractor, non-malleable, privacy, codes} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Dean Doron, Pooya Hatami, and William M. Hoza. Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 16:1-16:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{doron_et_al:LIPIcs.CCC.2019.16, author = {Doron, Dean and Hatami, Pooya and Hoza, William M.}, title = {{Near-Optimal Pseudorandom Generators for Constant-Depth Read-Once Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {16:1--16:34}, 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.16}, URN = {urn:nbn:de:0030-drops-108382}, doi = {10.4230/LIPIcs.CCC.2019.16}, annote = {Keywords: Pseudorandom generators, Constant-depth formulas, Explicit constructions} }
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} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
William M. Hoza. Typically-Correct Derandomization for Small Time and Space. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 9:1-9:39, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hoza:LIPIcs.CCC.2019.9, author = {Hoza, William M.}, title = {{Typically-Correct Derandomization for Small Time and Space}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {9:1--9:39}, 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.9}, URN = {urn:nbn:de:0030-drops-108317}, doi = {10.4230/LIPIcs.CCC.2019.9}, annote = {Keywords: Derandomization, pseudorandomness, space complexity} }
Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Alexander Golovnev, Alexander S. Kulikov, Alexander V. Smal, and Suguru Tamaki. Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{golovnev_et_al:LIPIcs.MFCS.2016.45, author = {Golovnev, Alexander and Kulikov, Alexander S. and Smal, Alexander V. and Tamaki, Suguru}, title = {{Circuit Size Lower Bounds and #SAT Upper Bounds Through a General Framework}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.45}, URN = {urn:nbn:de:0030-drops-64588}, doi = {10.4230/LIPIcs.MFCS.2016.45}, annote = {Keywords: circuit complexity, lower bounds, exponential time algorithms, satisfiability} }
Feedback for Dagstuhl Publishing