Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, and Madhu Sudan. Is This Correct? Let’s Check!. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 15:1-15:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2023.15, author = {Ben-Eliezer, Omri and Mikulincer, Dan and Mossel, Elchanan and Sudan, Madhu}, title = {{Is This Correct? Let’s Check!}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {15:1--15:11}, 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.15}, URN = {urn:nbn:de:0030-drops-175180}, doi = {10.4230/LIPIcs.ITCS.2023.15}, annote = {Keywords: Error Propagation, Preferential Attachment} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Omri Ben-Eliezer, Shoham Letzter, and Erik Waingarten. Finding Monotone Patterns in Sublinear Time, Adaptively. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 17:1-17:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{beneliezer_et_al:LIPIcs.ICALP.2022.17, author = {Ben-Eliezer, Omri and Letzter, Shoham and Waingarten, Erik}, title = {{Finding Monotone Patterns in Sublinear Time, Adaptively}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {17:1--17:19}, 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.17}, URN = {urn:nbn:de:0030-drops-163586}, doi = {10.4230/LIPIcs.ICALP.2022.17}, annote = {Keywords: property testing, monotone patterns, monotone decomposition, adaptivity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ilan Newman and Nithin Varma. Strongly Sublinear Algorithms for Testing Pattern Freeness. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 98:1-98:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{newman_et_al:LIPIcs.ICALP.2022.98, author = {Newman, Ilan and Varma, Nithin}, title = {{Strongly Sublinear Algorithms for Testing Pattern Freeness}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {98:1--98: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.98}, URN = {urn:nbn:de:0030-drops-164390}, doi = {10.4230/LIPIcs.ICALP.2022.98}, annote = {Keywords: Property testing, Pattern freeness, Sublinear algorithms} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Yuichi Yoshida. Ordered Graph Limits and Their Applications. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 42:1-42:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2021.42, author = {Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Yoshida, Yuichi}, title = {{Ordered Graph Limits and Their Applications}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {42:1--42: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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.42}, URN = {urn:nbn:de:0030-drops-135815}, doi = {10.4230/LIPIcs.ITCS.2021.42}, annote = {Keywords: graph limits, ordered graph, graphon, cut distance, removal lemma} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Omri Ben-Eliezer, Eldar Fischer, Amit Levi, and Ron D. Rothblum. Hard Properties with (Very) Short PCPPs and Their Applications. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 9:1-9:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2020.9, author = {Ben-Eliezer, Omri and Fischer, Eldar and Levi, Amit and Rothblum, Ron D.}, title = {{Hard Properties with (Very) Short PCPPs and Their Applications}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {9:1--9:27}, 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.9}, URN = {urn:nbn:de:0030-drops-116949}, doi = {10.4230/LIPIcs.ITCS.2020.9}, annote = {Keywords: PCPP, Property testing, Tolerant testing, Erasure resilient testing, Randomized encoding, Coding theory} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Omri Ben-Eliezer. Testing Local Properties of Arrays. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 11:1-11:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{beneliezer:LIPIcs.ITCS.2019.11, author = {Ben-Eliezer, Omri}, title = {{Testing Local Properties of Arrays}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {11:1--11:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.11}, URN = {urn:nbn:de:0030-drops-101041}, doi = {10.4230/LIPIcs.ITCS.2019.11}, annote = {Keywords: Property Testing, Local Properties, Monotonicity Testing, Hypergrid, Pattern Matching} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Omri Ben-Eliezer and Eldar Fischer. Earthmover Resilience and Testing in Ordered Structures. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 18:1-18:35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{beneliezer_et_al:LIPIcs.CCC.2018.18, author = {Ben-Eliezer, Omri and Fischer, Eldar}, title = {{Earthmover Resilience and Testing in Ordered Structures}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {18:1--18:35}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.18}, URN = {urn:nbn:de:0030-drops-88718}, doi = {10.4230/LIPIcs.CCC.2018.18}, annote = {Keywords: characterizations of testability, distance estimation, earthmover resilient, ordered structures, property testing} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Noga Alon and Omri Ben-Eliezer. Efficient Removal Lemmas for Matrices. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 25:1-25:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{alon_et_al:LIPIcs.APPROX-RANDOM.2017.25, author = {Alon, Noga and Ben-Eliezer, Omri}, title = {{Efficient Removal Lemmas for Matrices}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {25:1--25:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.25}, URN = {urn:nbn:de:0030-drops-75744}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.25}, annote = {Keywords: Property Testing, Removal Lemma, Matrix Regularity Lemma, Binary Matrix} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Omri Ben-Eliezer, Simon Korman, and Daniel Reichman. Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 9:1-9:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{beneliezer_et_al:LIPIcs.ICALP.2017.9, author = {Ben-Eliezer, Omri and Korman, Simon and Reichman, Daniel}, title = {{Deleting and Testing Forbidden Patterns in Multi-Dimensional Arrays}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.9}, URN = {urn:nbn:de:0030-drops-74427}, doi = {10.4230/LIPIcs.ICALP.2017.9}, annote = {Keywords: Property testing, Sublinear algorithms, Pattern matching} }
Feedback for Dagstuhl Publishing