Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Ashish Dwivedi, Zeyu Guo, and Ben Lee Volk. Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 44:1-44:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dwivedi_et_al:LIPIcs.APPROX/RANDOM.2024.44, author = {Dwivedi, Ashish and Guo, Zeyu and Volk, Ben Lee}, title = {{Optimal Pseudorandom Generators for Low-Degree Polynomials over Moderately Large Fields}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {44:1--44:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.44}, URN = {urn:nbn:de:0030-drops-210370}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.44}, annote = {Keywords: Pseudorandom Generators, Low Degree Polynomials} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Reut Levi, Moti Medina, and Omer Tubul. Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 60:1-60:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{levi_et_al:LIPIcs.APPROX/RANDOM.2024.60, author = {Levi, Reut and Medina, Moti and Tubul, Omer}, title = {{Nearly Optimal Local Algorithms for Constructing Sparse Spanners of Clusterable Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {60:1--60:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.60}, URN = {urn:nbn:de:0030-drops-210537}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.60}, annote = {Keywords: Locally Computable Algorithms, Sublinear algorithms, Spanning Subgraphs, Clusterbale Graphs} }
Published in: LIPIcs, Volume 304, 5th Conference on Information-Theoretic Cryptography (ITC 2024)
D'or Banoun, Elette Boyle, and Ran Cohen. Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond. In 5th Conference on Information-Theoretic Cryptography (ITC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 304, pp. 1:1-1:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{banoun_et_al:LIPIcs.ITC.2024.1, author = {Banoun, D'or and Boyle, Elette and Cohen, Ran}, title = {{Information-Theoretic Topology-Hiding Broadcast: Wheels, Stars, Friendship, and Beyond}}, booktitle = {5th Conference on Information-Theoretic Cryptography (ITC 2024)}, pages = {1:1--1:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-333-1}, ISSN = {1868-8969}, year = {2024}, volume = {304}, editor = {Aggarwal, Divesh}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2024.1}, URN = {urn:nbn:de:0030-drops-205090}, doi = {10.4230/LIPIcs.ITC.2024.1}, annote = {Keywords: broadcast, topology-hiding protocols, information-theoretic security} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Itai Boneh, Shay Golan, Shay Mozes, and Oren Weimann. Õptimal Dynamic Time Warping on Run-Length Encoded Strings. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{boneh_et_al:LIPIcs.ICALP.2024.30, author = {Boneh, Itai and Golan, Shay and Mozes, Shay and Weimann, Oren}, title = {{\~{O}ptimal Dynamic Time Warping on Run-Length Encoded Strings}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {30:1--30:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.30}, URN = {urn:nbn:de:0030-drops-201730}, doi = {10.4230/LIPIcs.ICALP.2024.30}, annote = {Keywords: Dynamic time warping, Fr\'{e}chet distance, edit distance, run-length encoding} }
Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)
Shaull Almagor, Daniel Assa, and Udi Boker. Synchronized CTL over One-Counter Automata. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 19:1-19:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{almagor_et_al:LIPIcs.FSTTCS.2023.19, author = {Almagor, Shaull and Assa, Daniel and Boker, Udi}, title = {{Synchronized CTL over One-Counter Automata}}, booktitle = {43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)}, pages = {19:1--19:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-304-1}, ISSN = {1868-8969}, year = {2023}, volume = {284}, editor = {Bouyer, Patricia and Srinivasan, Srikanth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.19}, URN = {urn:nbn:de:0030-drops-193921}, doi = {10.4230/LIPIcs.FSTTCS.2023.19}, annote = {Keywords: CTL, Synchronization, One Counter Automata, Model Checking} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Prahladh Harsha, Daniel Mitropolsky, and Alon Rosen. Downward Self-Reducibility in TFNP. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 67:1-67:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{harsha_et_al:LIPIcs.ITCS.2023.67, author = {Harsha, Prahladh and Mitropolsky, Daniel and Rosen, Alon}, title = {{Downward Self-Reducibility in TFNP}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {67:1--67:17}, 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.67}, URN = {urn:nbn:de:0030-drops-175700}, doi = {10.4230/LIPIcs.ITCS.2023.67}, annote = {Keywords: downward self-reducibility, TFNP, TFUP, factoring, PLS, CLS} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Hermish Mehta and Daniel Reichman. Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 7:1-7:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mehta_et_al:LIPIcs.APPROX/RANDOM.2022.7, author = {Mehta, Hermish and Reichman, Daniel}, title = {{Local Treewidth of Random and Noisy Graphs with Applications to Stopping Contagion in Networks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {7:1--7: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.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.7}, URN = {urn:nbn:de:0030-drops-171299}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.7}, annote = {Keywords: Graph Algorithms, Random Graphs, Data Structures and Algorithms, Discrete Mathematics} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Surbhi Goel, Adam Klivans, Pasin Manurangsi, and Daniel Reichman. Tight Hardness Results for Training Depth-2 ReLU Networks. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 22:1-22:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{goel_et_al:LIPIcs.ITCS.2021.22, author = {Goel, Surbhi and Klivans, Adam and Manurangsi, Pasin and Reichman, Daniel}, title = {{Tight Hardness Results for Training Depth-2 ReLU Networks}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {22:1--22:14}, 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.22}, URN = {urn:nbn:de:0030-drops-135611}, doi = {10.4230/LIPIcs.ITCS.2021.22}, annote = {Keywords: ReLU, Learning Algorithm, Running Time Lower Bound} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Alexander Golovnev, Mika Göös, Daniel Reichman, and Igor Shinkar. String Matching: Communication, Circuits, and Learning. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 56:1-56:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{golovnev_et_al:LIPIcs.APPROX-RANDOM.2019.56, author = {Golovnev, Alexander and G\"{o}\"{o}s, Mika and Reichman, Daniel and Shinkar, Igor}, title = {{String Matching: Communication, Circuits, and Learning}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {56:1--56:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-125-2}, ISSN = {1868-8969}, year = {2019}, volume = {145}, editor = {Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.56}, URN = {urn:nbn:de:0030-drops-112717}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.56}, annote = {Keywords: string matching, communication complexity, circuit complexity, PAC learning} }
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} }
Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Huck Bennett, Daniel Reichman, and Igor Shinkar. On Percolation and NP-Hardness. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 80:1-80:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{bennett_et_al:LIPIcs.ICALP.2016.80, author = {Bennett, Huck and Reichman, Daniel and Shinkar, Igor}, title = {{On Percolation and NP-Hardness}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {80:1--80:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.80}, URN = {urn:nbn:de:0030-drops-62056}, doi = {10.4230/LIPIcs.ICALP.2016.80}, annote = {Keywords: percolation, NP-hardness, random subgraphs, chromatic number} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Michael Krivelevich, Daniel Reichman, and Wojciech Samotij. Smoothed Analysis on Connected Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 810-825, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{krivelevich_et_al:LIPIcs.APPROX-RANDOM.2014.810, author = {Krivelevich, Michael and Reichman, Daniel and Samotij, Wojciech}, title = {{Smoothed Analysis on Connected Graphs}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {810--825}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.810}, URN = {urn:nbn:de:0030-drops-47407}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.810}, annote = {Keywords: Random walks and Markov chains, Random network models} }
Feedback for Dagstuhl Publishing