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 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 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ofer Grossman and Justin Holmgren. Error Correcting Codes for Uncompressed Messages. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{grossman_et_al:LIPIcs.ITCS.2021.43, author = {Grossman, Ofer and Holmgren, Justin}, title = {{Error Correcting Codes for Uncompressed Messages}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {43:1--43:18}, 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.43}, URN = {urn:nbn:de:0030-drops-135828}, doi = {10.4230/LIPIcs.ITCS.2021.43}, annote = {Keywords: Coding Theory, List Decoding} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Klim Efremenko, Elad Haramaty, and Yael Tauman Kalai. Interactive Coding with Constant Round and Communication Blowup. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 7:1-7:34, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2020.7, author = {Efremenko, Klim and Haramaty, Elad and Kalai, Yael Tauman}, title = {{Interactive Coding with Constant Round and Communication Blowup}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {7:1--7:34}, 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.7}, URN = {urn:nbn:de:0030-drops-116927}, doi = {10.4230/LIPIcs.ITCS.2020.7}, annote = {Keywords: Interactive Coding, Round Complexity, Error Correcting Codes} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Badih Ghazi, Elad Haramaty, Pritish Kamath, and Madhu Sudan. Compression in a Distributed Setting. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{ghazi_et_al:LIPIcs.ITCS.2017.19, author = {Ghazi, Badih and Haramaty, Elad and Kamath, Pritish and Sudan, Madhu}, title = {{Compression in a Distributed Setting}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {19:1--19:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.19}, URN = {urn:nbn:de:0030-drops-81763}, doi = {10.4230/LIPIcs.ITCS.2017.19}, annote = {Keywords: Distributed Compression, Communication, Language Evolution, Isolating Hash Families} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Elad Haramaty, Chin Ho Lee, and Emanuele Viola. Bounded Independence Plus Noise Fools Products. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 14:1-14:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{haramaty_et_al:LIPIcs.CCC.2017.14, author = {Haramaty, Elad and Lee, Chin Ho and Viola, Emanuele}, title = {{Bounded Independence Plus Noise Fools Products}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {14:1--14:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.14}, URN = {urn:nbn:de:0030-drops-75188}, doi = {10.4230/LIPIcs.CCC.2017.14}, annote = {Keywords: ounded independence, Noise, Product tests, Error-correcting codes, Pseudorandomness} }