Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {8:1--8:16}, 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.8}, URN = {urn:nbn:de:0030-drops-204045}, doi = {10.4230/LIPIcs.CCC.2024.8}, annote = {Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, Ran Raz, and Raghuvansh R. Saxena. Information Dissemination via Broadcasts in the Presence of Adversarial Noise. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 19:1-19:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{efremenko_et_al:LIPIcs.CCC.2024.19, author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Raz, Ran and Saxena, Raghuvansh R.}, title = {{Information Dissemination via Broadcasts in the Presence of Adversarial Noise}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {19:1--19:33}, 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.19}, URN = {urn:nbn:de:0030-drops-204159}, doi = {10.4230/LIPIcs.CCC.2024.19}, annote = {Keywords: Radio Networks, Interactive Coding, Error Correcting Codes} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Sreejata Kishor Bhattacharya, Arkadev Chattopadhyay, and Pavel Dvořák. Exponential Separation Between Powers of Regular and General Resolution over Parities. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 23:1-23:32, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bhattacharya_et_al:LIPIcs.CCC.2024.23, author = {Bhattacharya, Sreejata Kishor and Chattopadhyay, Arkadev and Dvo\v{r}\'{a}k, Pavel}, title = {{Exponential Separation Between Powers of Regular and General Resolution over Parities}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {23:1--23:32}, 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.23}, URN = {urn:nbn:de:0030-drops-204191}, doi = {10.4230/LIPIcs.CCC.2024.23}, annote = {Keywords: Proof Complexity, Regular Reslin, Branching Programs, Lifting} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Protecting Single-Hop Radio Networks from Message Drops. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 53:1-53:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{efremenko_et_al:LIPIcs.ICALP.2023.53, author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.}, title = {{Protecting Single-Hop Radio Networks from Message Drops}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {53:1--53: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.53}, URN = {urn:nbn:de:0030-drops-181059}, doi = {10.4230/LIPIcs.ICALP.2023.53}, annote = {Keywords: Radio Networks, Interactive Coding, Error Correcting Codes} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2023.46, author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.}, title = {{Noisy Radio Network Lower Bounds via Noiseless Beeping Lower Bounds}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {46:1--46:20}, 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.46}, URN = {urn:nbn:de:0030-drops-175499}, doi = {10.4230/LIPIcs.ITCS.2023.46}, annote = {Keywords: Beeping Model, Radio Networks} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, and Toniann Pitassi. Secret Sharing, Slice Formulas, and Monotone Real Circuits. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{applebaum_et_al:LIPIcs.ITCS.2022.8, author = {Applebaum, Benny and Beimel, Amos and Nir, Oded and Peter, Naty and Pitassi, Toniann}, title = {{Secret Sharing, Slice Formulas, and Monotone Real Circuits}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {8:1--8: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.8}, URN = {urn:nbn:de:0030-drops-156046}, doi = {10.4230/LIPIcs.ITCS.2022.8}, annote = {Keywords: Secret Sharing Schemes, Monotone Real Circuits} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Klim Efremenko, Gillat Kol, Dmitry Paramonov, and Raghuvansh R. Saxena. Computation over the Noisy Broadcast Channel with Malicious Parties. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 82:1-82:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2021.82, author = {Efremenko, Klim and Kol, Gillat and Paramonov, Dmitry and Saxena, Raghuvansh R.}, title = {{Computation over the Noisy Broadcast Channel with Malicious Parties}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {82:1--82: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.82}, URN = {urn:nbn:de:0030-drops-136215}, doi = {10.4230/LIPIcs.ITCS.2021.82}, annote = {Keywords: Broadcast Network, Malicious Parties, Communication Complexity} }
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 137, 34th Computational Complexity Conference (CCC 2019)
Mark Braverman, Klim Efremenko, Ran Gelles, and Michael A. Yitayew. Optimal Short-Circuit Resilient Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 10:1-10:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{braverman_et_al:LIPIcs.CCC.2019.10, author = {Braverman, Mark and Efremenko, Klim and Gelles, Ran and Yitayew, Michael A.}, title = {{Optimal Short-Circuit Resilient Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {10:1--10:22}, 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.10}, URN = {urn:nbn:de:0030-drops-108326}, doi = {10.4230/LIPIcs.CCC.2019.10}, annote = {Keywords: Circuit Complexity, Noise-Resilient Circuits, Interactive Coding, Coding Theory, Karchmer-Wigderson Games} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Klim Efremenko, Ankit Garg, Rafael Oliveira, and Avi Wigderson. Barriers for Rank Methods in Arithmetic Complexity. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 1:1-1:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{efremenko_et_al:LIPIcs.ITCS.2018.1, author = {Efremenko, Klim and Garg, Ankit and Oliveira, Rafael and Wigderson, Avi}, title = {{Barriers for Rank Methods in Arithmetic Complexity}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {1:1--1:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.1}, URN = {urn:nbn:de:0030-drops-83506}, doi = {10.4230/LIPIcs.ITCS.2018.1}, annote = {Keywords: Lower Bounds, Barriers, Partial Derivatives, Flattenings, Algebraic Complexity} }