Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Omri Ben-Eliezer, Esty Kelman, Uri Meir, and Sofya Raskhodnikova. Property Testing with Online Adversaries. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 11:1-11:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2024.11, author = {Ben-Eliezer, Omri and Kelman, Esty and Meir, Uri and Raskhodnikova, Sofya}, title = {{Property Testing with Online Adversaries}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {11:1--11:25}, 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.11}, URN = {urn:nbn:de:0030-drops-195395}, doi = {10.4230/LIPIcs.ITCS.2024.11}, annote = {Keywords: Linearity testing, low-degree testing, Reed-Muller codes, testing properties of sequences, erasure-resilience, corruption-resilience} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Uri Meir, Rotem Oshman, Ofer Shayevitz, and Yuval Volkov. Resilience of 3-Majority Dynamics to Non-Uniform Schedulers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 86:1-86:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{meir_et_al:LIPIcs.ITCS.2023.86, author = {Meir, Uri and Oshman, Rotem and Shayevitz, Ofer and Volkov, Yuval}, title = {{Resilience of 3-Majority Dynamics to Non-Uniform Schedulers}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {86:1--86:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.86}, URN = {urn:nbn:de:0030-drops-175895}, doi = {10.4230/LIPIcs.ITCS.2023.86}, annote = {Keywords: chemical reaction networks, population protocols, randomized scheduler} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Yahel Manor and Or Meir. Lifting with Inner Functions of Polynomial Discrepancy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 26:1-26:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{manor_et_al:LIPIcs.APPROX/RANDOM.2022.26, author = {Manor, Yahel and Meir, Or}, title = {{Lifting with Inner Functions of Polynomial Discrepancy}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {26:1--26:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, 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.2022.26}, URN = {urn:nbn:de:0030-drops-171486}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.26}, annote = {Keywords: Lifting, communication complexity, query complexity, discrepancy} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Michael Ezra and Ron D. Rothblum. Small Circuits Imply Efficient Arthur-Merlin Protocols. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 67:1-67:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ezra_et_al:LIPIcs.ITCS.2022.67, author = {Ezra, Michael and Rothblum, Ron D.}, title = {{Small Circuits Imply Efficient Arthur-Merlin Protocols}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {67:1--67:16}, 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.67}, URN = {urn:nbn:de:0030-drops-156635}, doi = {10.4230/LIPIcs.ITCS.2022.67}, annote = {Keywords: Circuits Complexity, Circuit Lower Bounds, Communication Complexity, Data Streaming, Arthur-Merlin games, Interactive Proofs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, and Dmitry Sokolov. The Power of Negative Reasoning. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 40:1-40:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{derezende_et_al:LIPIcs.CCC.2021.40, author = {de Rezende, Susanna F. and Lauria, Massimo and Nordstr\"{o}m, Jakob and Sokolov, Dmitry}, title = {{The Power of Negative Reasoning}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {40:1--40: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.40}, URN = {urn:nbn:de:0030-drops-143140}, doi = {10.4230/LIPIcs.CCC.2021.40}, annote = {Keywords: Proof complexity, Polynomial calculus, Nullstellensatz, Sums-of-squares, Sherali-Adams} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Uri Meir. Comparison Graphs: A Unified Method for Uniformity Testing. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 17:1-17:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{meir:LIPIcs.ITCS.2021.17, author = {Meir, Uri}, title = {{Comparison Graphs: A Unified Method for Uniformity Testing}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {17:1--17:20}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.17}, URN = {urn:nbn:de:0030-drops-135560}, doi = {10.4230/LIPIcs.ITCS.2021.17}, annote = {Keywords: Distribution Testing, Uniformity Testing, Distributed Algorithms, Streaming Algorithms, Comparison Graphs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Filmus, Or Meir, and Avishay Tal. Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0 (Extended Abstract). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 89:1-89:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{filmus_et_al:LIPIcs.ITCS.2021.89, author = {Filmus, Yuval and Meir, Or and Tal, Avishay}, title = {{Shrinkage Under Random Projections, and Cubic Formula Lower Bounds for AC0}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {89:1--89:7}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.89}, URN = {urn:nbn:de:0030-drops-136281}, doi = {10.4230/LIPIcs.ITCS.2021.89}, annote = {Keywords: De Morgan formulas, KRW Conjecture, shrinkage, random restrictions, random projections, bounded depth circuits, constant depth circuits, formula complexity} }
Published in: LIPIcs, Volume 150, 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)
Toniann Pitassi. Progress in Lifting and Applications in Lower Bounds (Invited Talk). In 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 150, p. 4:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{pitassi:LIPIcs.FSTTCS.2019.4, author = {Pitassi, Toniann}, title = {{Progress in Lifting and Applications in Lower Bounds}}, booktitle = {39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2019)}, pages = {4:1--4:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-131-3}, ISSN = {1868-8969}, year = {2019}, volume = {150}, editor = {Chattopadhyay, Arkadev and Gastin, Paul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2019.4}, URN = {urn:nbn:de:0030-drops-115664}, doi = {10.4230/LIPIcs.FSTTCS.2019.4}, annote = {Keywords: complexity theory, lower bounds, communication complexity} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Benjamin Rossman. Criticality of Regular Formulas. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 1:1-1:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{rossman:LIPIcs.CCC.2019.1, author = {Rossman, Benjamin}, title = {{Criticality of Regular Formulas}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {1:1--1:28}, 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.1}, URN = {urn:nbn:de:0030-drops-108230}, doi = {10.4230/LIPIcs.CCC.2019.1}, annote = {Keywords: AC^0 circuits, formulas, criticality} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Susanna F. de Rezende, Jakob Nordström, Or Meir, and Robert Robere. Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{derezende_et_al:LIPIcs.CCC.2019.18, author = {de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Meir, Or and Robere, Robert}, title = {{Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {18:1--18:16}, 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.18}, URN = {urn:nbn:de:0030-drops-108403}, doi = {10.4230/LIPIcs.CCC.2019.18}, annote = {Keywords: proof complexity, Nullstellensatz, pebble games, trade-offs, size, degree} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. Query-To-Communication Lifting for BPP Using Inner Product. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 35:1-35:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chattopadhyay_et_al:LIPIcs.ICALP.2019.35, author = {Chattopadhyay, Arkadev and Filmus, Yuval and Koroth, Sajin and Meir, Or and Pitassi, Toniann}, title = {{Query-To-Communication Lifting for BPP Using Inner Product}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {35:1--35:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.35}, URN = {urn:nbn:de:0030-drops-106110}, doi = {10.4230/LIPIcs.ICALP.2019.35}, annote = {Keywords: lifting theorems, inner product, BPP Lifting, Deterministic Lifting} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Bruno Loff and Sagnik Mukhopadhyay. Lifting Theorems for Equality. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 50:1-50:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{loff_et_al:LIPIcs.STACS.2019.50, author = {Loff, Bruno and Mukhopadhyay, Sagnik}, title = {{Lifting Theorems for Equality}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {50:1--50:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.50}, URN = {urn:nbn:de:0030-drops-102892}, doi = {10.4230/LIPIcs.STACS.2019.50}, annote = {Keywords: Communication complexity, Query complexity, Simulation theorem, Equality function} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Sajin Koroth and Or Meir. Improved Composition Theorems for Functions and Relations. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 48:1-48:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{koroth_et_al:LIPIcs.APPROX-RANDOM.2018.48, author = {Koroth, Sajin and Meir, Or}, title = {{Improved Composition Theorems for Functions and Relations}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {48:1--48:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, 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.2018.48}, URN = {urn:nbn:de:0030-drops-94525}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.48}, annote = {Keywords: circuit complexity, communication complexity, KRW conjecture, composition} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Irit Dinur and Or Meir. Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 3:1-3:51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{dinur_et_al:LIPIcs.CCC.2016.3, author = {Dinur, Irit and Meir, Or}, title = {{Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {3:1--3:51}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.3}, URN = {urn:nbn:de:0030-drops-58412}, doi = {10.4230/LIPIcs.CCC.2016.3}, annote = {Keywords: Formula lower bounds, communication complexity, Karchmer-Wigderson games, KRW composition conjecture} }
Feedback for Dagstuhl Publishing