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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Nikhil Gupta and Chandan Saha. On the Symmetries of and Equivalence Test for Design Polynomials. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 53:1-53:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gupta_et_al:LIPIcs.MFCS.2019.53, author = {Gupta, Nikhil and Saha, Chandan}, title = {{On the Symmetries of and Equivalence Test for Design Polynomials}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {53:1--53:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.53}, URN = {urn:nbn:de:0030-drops-109979}, doi = {10.4230/LIPIcs.MFCS.2019.53}, annote = {Keywords: Nisan-Wigderson design polynomial, characterization by symmetries, Lie algebra, group of symmetries, circuit testability, flip theorem, equivalence test} }
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} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Bernhard Haeupler, Pritish Kamath, and Ameya Velingker. Communication with Partial Noiseless Feedback. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 881-897, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{haeupler_et_al:LIPIcs.APPROX-RANDOM.2015.881, author = {Haeupler, Bernhard and Kamath, Pritish and Velingker, Ameya}, title = {{Communication with Partial Noiseless Feedback}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {881--897}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.881}, URN = {urn:nbn:de:0030-drops-53426}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.881}, annote = {Keywords: Communication with feedback, Interactive communication, Coding theory Digital} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Abhishek Bhowmick and Shachar Lovett. Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 72-87, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bhowmick_et_al:LIPIcs.CCC.2015.72, author = {Bhowmick, Abhishek and Lovett, Shachar}, title = {{Nonclassical Polynomials as a Barrier to Polynomial Lower Bounds}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {72--87}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.72}, URN = {urn:nbn:de:0030-drops-50491}, doi = {10.4230/LIPIcs.CCC.2015.72}, annote = {Keywords: nonclassical polynomials, polynomials, lower bounds, barrier} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong Locally Testable Codes with Relaxed Local Decoders. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 1-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{goldreich_et_al:LIPIcs.CCC.2015.1, author = {Goldreich, Oded and Gur, Tom and Komargodski, Ilan}, title = {{Strong Locally Testable Codes with Relaxed Local Decoders}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {1--41}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.1}, URN = {urn:nbn:de:0030-drops-50507}, doi = {10.4230/LIPIcs.CCC.2015.1}, annote = {Keywords: Locally Testable Codes, Locally Decodable Codes, PCPs of Proximity} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian. Verifiable Stream Computation and Arthur–Merlin Communication. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 217-243, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{chakrabarti_et_al:LIPIcs.CCC.2015.217, author = {Chakrabarti, Amit and Cormode, Graham and McGregor, Andrew and Thaler, Justin and Venkatasubramanian, Suresh}, title = {{Verifiable Stream Computation and Arthur–Merlin Communication}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {217--243}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.217}, URN = {urn:nbn:de:0030-drops-50680}, doi = {10.4230/LIPIcs.CCC.2015.217}, annote = {Keywords: Arthur-Merlin communication complexity, streaming interactive proofs} }
Feedback for Dagstuhl Publishing