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 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yael Hitron, Merav Parter, and Eylon Yogev. Secure Distributed Network Optimization Against Eavesdroppers. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 71:1-71:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hitron_et_al:LIPIcs.ITCS.2023.71, author = {Hitron, Yael and Parter, Merav and Yogev, Eylon}, title = {{Secure Distributed Network Optimization Against Eavesdroppers}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {71:1--71: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.71}, URN = {urn:nbn:de:0030-drops-175746}, doi = {10.4230/LIPIcs.ITCS.2023.71}, annote = {Keywords: congest, secure computation, network optimization} }
Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)
Yael Hitron, Merav Parter, and Eylon Yogev. Broadcast CONGEST Algorithms Against Eavesdroppers. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 27:1-27:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{hitron_et_al:LIPIcs.DISC.2022.27, author = {Hitron, Yael and Parter, Merav and Yogev, Eylon}, title = {{Broadcast CONGEST Algorithms Against Eavesdroppers}}, booktitle = {36th International Symposium on Distributed Computing (DISC 2022)}, pages = {27:1--27:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-255-6}, ISSN = {1868-8969}, year = {2022}, volume = {246}, editor = {Scheideler, Christian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.27}, URN = {urn:nbn:de:0030-drops-172186}, doi = {10.4230/LIPIcs.DISC.2022.27}, annote = {Keywords: congest, edge-connectivity, secret sharing} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Gal Arnon, Alessandro Chiesa, and Eylon Yogev. Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 24:1-24:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{arnon_et_al:LIPIcs.CCC.2022.24, author = {Arnon, Gal and Chiesa, Alessandro and Yogev, Eylon}, title = {{Hardness of Approximation for Stochastic Problems via Interactive Oracle Proofs}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {24:1--24:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-241-9}, ISSN = {1868-8969}, year = {2022}, volume = {234}, editor = {Lovett, Shachar}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.24}, URN = {urn:nbn:de:0030-drops-165867}, doi = {10.4230/LIPIcs.CCC.2022.24}, annote = {Keywords: hardness of approximation, interactive oracle proofs, stochastic satisfaction problems} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Boaz Menuhin and Moni Naor. Keep That Card in Mind: Card Guessing with Limited Memory. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 107:1-107:28, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{menuhin_et_al:LIPIcs.ITCS.2022.107, author = {Menuhin, Boaz and Naor, Moni}, title = {{Keep That Card in Mind: Card Guessing with Limited Memory}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {107:1--107:28}, 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.107}, URN = {urn:nbn:de:0030-drops-157039}, doi = {10.4230/LIPIcs.ITCS.2022.107}, annote = {Keywords: Adaptivity vs Non-adaptivity, Adversarial Robustness, Card Guessing, Compression Argument, Information Theory, Streaming Algorithms, Two Player Game} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Yael Hitron and Merav Parter. Broadcast CONGEST Algorithms against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 23:1-23:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hitron_et_al:LIPIcs.DISC.2021.23, author = {Hitron, Yael and Parter, Merav}, title = {{Broadcast CONGEST Algorithms against Adversarial Edges}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {23:1--23:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.23}, URN = {urn:nbn:de:0030-drops-148256}, doi = {10.4230/LIPIcs.DISC.2021.23}, annote = {Keywords: CONGEST, Fault-Tolerant Network Design, Edge Connectivity} }
Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)
Yael Hitron and Merav Parter. General CONGEST Compilers against Adversarial Edges. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 24:1-24:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{hitron_et_al:LIPIcs.DISC.2021.24, author = {Hitron, Yael and Parter, Merav}, title = {{General CONGEST Compilers against Adversarial Edges}}, booktitle = {35th International Symposium on Distributed Computing (DISC 2021)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-210-5}, ISSN = {1868-8969}, year = {2021}, volume = {209}, editor = {Gilbert, Seth}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.24}, URN = {urn:nbn:de:0030-drops-148266}, doi = {10.4230/LIPIcs.DISC.2021.24}, annote = {Keywords: CONGEST, Cycle Covers, Byzantine Adversaries} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Robert Kleinberg, Oliver Korten, Daniel Mitropolsky, and Christos Papadimitriou. Total Functions in the Polynomial Hierarchy. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 44:1-44:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{kleinberg_et_al:LIPIcs.ITCS.2021.44, author = {Kleinberg, Robert and Korten, Oliver and Mitropolsky, Daniel and Papadimitriou, Christos}, title = {{Total Functions in the Polynomial Hierarchy}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {44:1--44:18}, 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.44}, URN = {urn:nbn:de:0030-drops-135835}, doi = {10.4230/LIPIcs.ITCS.2021.44}, annote = {Keywords: total complexity, polynomial hierarchy, pigeonhole principle} }
Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)
Yael Hitron, Cameron Musco, and Merav Parter. Spiking Neural Networks Through the Lens of Streaming Algorithms. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 10:1-10:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{hitron_et_al:LIPIcs.DISC.2020.10, author = {Hitron, Yael and Musco, Cameron and Parter, Merav}, title = {{Spiking Neural Networks Through the Lens of Streaming Algorithms}}, booktitle = {34th International Symposium on Distributed Computing (DISC 2020)}, pages = {10:1--10:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-168-9}, ISSN = {1868-8969}, year = {2020}, volume = {179}, editor = {Attiya, Hagit}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.10}, URN = {urn:nbn:de:0030-drops-130882}, doi = {10.4230/LIPIcs.DISC.2020.10}, annote = {Keywords: Biological distributed algorithms, Spiking neural networks, Streaming algorithms} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Elazar Goldenberg and Karthik C. S.. Hardness Amplification of Optimization Problems. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 1:1-1:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{goldenberg_et_al:LIPIcs.ITCS.2020.1, author = {Goldenberg, Elazar and Karthik C. S.}, title = {{Hardness Amplification of Optimization Problems}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {1:1--1:13}, 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.1}, URN = {urn:nbn:de:0030-drops-116863}, doi = {10.4230/LIPIcs.ITCS.2020.1}, annote = {Keywords: hardness amplification, average case complexity, direct product, optimization problems, fine-grained complexity, TFNP} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Orr Paradise. Smooth and Strong PCPs. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 2:1-2:41, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{paradise:LIPIcs.ITCS.2020.2, author = {Paradise, Orr}, title = {{Smooth and Strong PCPs}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {2:1--2:41}, 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.2}, URN = {urn:nbn:de:0030-drops-116875}, doi = {10.4230/LIPIcs.ITCS.2020.2}, annote = {Keywords: Interactive and probabilistic proof systems, Probabilistically checkable proofs, Hardness of approximation} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Yael Hitron and Merav Parter. Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 57:1-57:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{hitron_et_al:LIPIcs.ESA.2019.57, author = {Hitron, Yael and Parter, Merav}, title = {{Counting to Ten with Two Fingers: Compressed Counting with Spiking Neurons}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {57:1--57:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.57}, URN = {urn:nbn:de:0030-drops-111782}, doi = {10.4230/LIPIcs.ESA.2019.57}, annote = {Keywords: stochastic neural networks, approximate counting, synchronizer} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Merav Parter and Eylon Yogev. Optimal Short Cycle Decomposition in Almost Linear Time. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 89:1-89:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{parter_et_al:LIPIcs.ICALP.2019.89, author = {Parter, Merav and Yogev, Eylon}, title = {{Optimal Short Cycle Decomposition in Almost Linear Time}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {89:1--89:14}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.89}, URN = {urn:nbn:de:0030-drops-106653}, doi = {10.4230/LIPIcs.ICALP.2019.89}, annote = {Keywords: Cycle decomposition, low-congestion cycle cover, graph sparsification} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Merav Parter and Eylon Yogev. Congested Clique Algorithms for Graph Spanners. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 40:1-40:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{parter_et_al:LIPIcs.DISC.2018.40, author = {Parter, Merav and Yogev, Eylon}, title = {{Congested Clique Algorithms for Graph Spanners}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {40:1--40:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.40}, URN = {urn:nbn:de:0030-drops-98298}, doi = {10.4230/LIPIcs.DISC.2018.40}, annote = {Keywords: Distributed Graph Algorithms, Spanner, Congested Clique} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Pavel Hubácek, Moni Naor, and Eylon Yogev. The Journey from NP to TFNP Hardness. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 60:1-60:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{hubacek_et_al:LIPIcs.ITCS.2017.60, author = {Hub\'{a}cek, Pavel and Naor, Moni and Yogev, Eylon}, title = {{The Journey from NP to TFNP Hardness}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {60:1--60:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.60}, URN = {urn:nbn:de:0030-drops-81627}, doi = {10.4230/LIPIcs.ITCS.2017.60}, annote = {Keywords: TFNP, derandomization, one-way functions, average-case hardness} }
Feedback for Dagstuhl Publishing