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