Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Ittai Rubinstein. Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 102:1-102:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rubinstein:LIPIcs.ICALP.2023.102, author = {Rubinstein, Ittai}, title = {{Average-Case to (Shifted) Worst-Case Reduction for the Trace Reconstruction Problem}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {102:1--102:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.102}, URN = {urn:nbn:de:0030-drops-181542}, doi = {10.4230/LIPIcs.ICALP.2023.102}, annote = {Keywords: Trace Reconstruction, Synchronization Channels, Computational Learning Theory, Computational Biology} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yujia Jin, Vidya Muthukumar, and Aaron Sidford. The Complexity of Infinite-Horizon General-Sum Stochastic Games. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 76:1-76:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{jin_et_al:LIPIcs.ITCS.2023.76, author = {Jin, Yujia and Muthukumar, Vidya and Sidford, Aaron}, title = {{The Complexity of Infinite-Horizon General-Sum Stochastic Games}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {76:1--76: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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.76}, URN = {urn:nbn:de:0030-drops-175791}, doi = {10.4230/LIPIcs.ITCS.2023.76}, annote = {Keywords: complexity, stochastic games, general-sum games, Nash equilibrium} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Pasin Manurangsi. Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 85:1-85:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{manurangsi:LIPIcs.ITCS.2023.85, author = {Manurangsi, Pasin}, title = {{Improved Inapproximability of VC Dimension and Littlestone’s Dimension via (Unbalanced) Biclique}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {85:1--85:18}, 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.85}, URN = {urn:nbn:de:0030-drops-175884}, doi = {10.4230/LIPIcs.ITCS.2023.85}, annote = {Keywords: VC Dimension, Littlestone’s Dimension, Maximum Biclique, Hardness of Approximation, Fine-Grained Complexity} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Aviad Rubinstein and Junyao Zhao. Beyond Worst-Case Budget-Feasible Mechanism Design. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 93:1-93:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2023.93, author = {Rubinstein, Aviad and Zhao, Junyao}, title = {{Beyond Worst-Case Budget-Feasible Mechanism Design}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {93:1--93:22}, 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.93}, URN = {urn:nbn:de:0030-drops-175969}, doi = {10.4230/LIPIcs.ITCS.2023.93}, annote = {Keywords: Procurement auctions, Mechanism design, Beyond worst-case analysis} }
Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)
Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran Tao. Further Collapses in TFNP. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 33:1-33:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{goos_et_al:LIPIcs.CCC.2022.33, author = {G\"{o}\"{o}s, Mika and Hollender, Alexandros and Jain, Siddhartha and Maystre, Gilbert and Pires, William and Robere, Robert and Tao, Ran}, title = {{Further Collapses in TFNP}}, booktitle = {37th Computational Complexity Conference (CCC 2022)}, pages = {33:1--33:15}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.33}, URN = {urn:nbn:de:0030-drops-165954}, doi = {10.4230/LIPIcs.CCC.2022.33}, annote = {Keywords: TFNP, PPAD, PLS, EOPL} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Ittai Rubinstein. Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 105:1-105:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{rubinstein:LIPIcs.ICALP.2022.105, author = {Rubinstein, Ittai}, title = {{Explicit and Efficient Construction of Nearly Optimal Rate Codes for the Binary Deletion Channel and the Poisson Repeat Channel}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {105:1--105:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.105}, URN = {urn:nbn:de:0030-drops-164466}, doi = {10.4230/LIPIcs.ICALP.2022.105}, annote = {Keywords: Error Correcting Codes, Algorithmic Coding Theory, Binary Deletion Channel} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Aviad Rubinstein and Junyao Zhao. Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 106:1-106:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{rubinstein_et_al:LIPIcs.ICALP.2022.106, author = {Rubinstein, Aviad and Zhao, Junyao}, title = {{Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {106:1--106:17}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.106}, URN = {urn:nbn:de:0030-drops-164478}, doi = {10.4230/LIPIcs.ICALP.2022.106}, annote = {Keywords: Submodular optimization, Fixed-parameter tractability, Random-order streaming} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Aviad Rubinstein and Junyao Zhao. Budget-Smoothed Analysis for Submodular Maximization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 113:1-113:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2022.113, author = {Rubinstein, Aviad and Zhao, Junyao}, title = {{Budget-Smoothed Analysis for Submodular Maximization}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {113:1--113:23}, 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.113}, URN = {urn:nbn:de:0030-drops-157095}, doi = {10.4230/LIPIcs.ITCS.2022.113}, annote = {Keywords: Submodular optimization, Beyond worst-case analysis, Greedy algorithms, Hardness of approximation} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Barna Saha. Sublinear Algorithms for Edit Distance (Invited Talk). In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, p. 5:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{saha:LIPIcs.MFCS.2021.5, author = {Saha, Barna}, title = {{Sublinear Algorithms for Edit Distance}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {5:1--5:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.5}, URN = {urn:nbn:de:0030-drops-144452}, doi = {10.4230/LIPIcs.MFCS.2021.5}, annote = {Keywords: Edit distance, sublinear algorithms, string processing} }
Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
Kuan Cheng, Alireza Farhadi, MohammadTaghi Hajiaghayi, Zhengzhong Jin, Xin Li, Aviad Rubinstein, Saeed Seddighin, and Yu Zheng. Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 54:1-54:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{cheng_et_al:LIPIcs.ICALP.2021.54, author = {Cheng, Kuan and Farhadi, Alireza and Hajiaghayi, MohammadTaghi and Jin, Zhengzhong and Li, Xin and Rubinstein, Aviad and Seddighin, Saeed and Zheng, Yu}, title = {{Streaming and Small Space Approximation Algorithms for Edit Distance and Longest Common Subsequence}}, booktitle = {48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)}, pages = {54:1--54:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-195-5}, ISSN = {1868-8969}, year = {2021}, volume = {198}, editor = {Bansal, Nikhil and Merelli, Emanuela and Worrell, James}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.54}, URN = {urn:nbn:de:0030-drops-141236}, doi = {10.4230/LIPIcs.ICALP.2021.54}, annote = {Keywords: Edit Distance, Longest Common Subsequence, Longest Increasing Subsequence, Space Efficient Algorithm, Approximation Algorithm} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Pasin Manurangsi, Aviad Rubinstein, and Tselil Schramm. The Strongish Planted Clique Hypothesis and Its Consequences. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 10:1-10:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{manurangsi_et_al:LIPIcs.ITCS.2021.10, author = {Manurangsi, Pasin and Rubinstein, Aviad and Schramm, Tselil}, title = {{The Strongish Planted Clique Hypothesis and Its Consequences}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {10:1--10:21}, 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.10}, URN = {urn:nbn:de:0030-drops-135491}, doi = {10.4230/LIPIcs.ITCS.2021.10}, annote = {Keywords: Planted Clique, Densest k-Subgraph, Hardness of Approximation} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Kousha Etessami, Christos Papadimitriou, Aviad Rubinstein, and Mihalis Yannakakis. Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 18:1-18:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{etessami_et_al:LIPIcs.ITCS.2020.18, author = {Etessami, Kousha and Papadimitriou, Christos and Rubinstein, Aviad and Yannakakis, Mihalis}, title = {{Tarski’s Theorem, Supermodular Games, and the Complexity of Equilibria}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {18:1--18:19}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.18}, URN = {urn:nbn:de:0030-drops-117037}, doi = {10.4230/LIPIcs.ITCS.2020.18}, annote = {Keywords: Tarski’s theorem, supermodular games, monotone functions, lattices, fixed points, Nash equilibria, computational complexity, PLS, PPAD, stochastic games, oracle model, lower bounds} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Aviad Rubinstein, Jack Z. Wang, and S. Matthew Weinberg. Optimal Single-Choice Prophet Inequalities from Samples. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 60:1-60:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{rubinstein_et_al:LIPIcs.ITCS.2020.60, author = {Rubinstein, Aviad and Wang, Jack Z. and Weinberg, S. Matthew}, title = {{Optimal Single-Choice Prophet Inequalities from Samples}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {60:1--60:10}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.60}, URN = {urn:nbn:de:0030-drops-117452}, doi = {10.4230/LIPIcs.ITCS.2020.60}, annote = {Keywords: Online algorithms, Probability, Optimization, Prophet inequalities, Samples, Auctions} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Rasmus Pagh, Nina Mesing Stausholm, and Mikkel Thorup. Hardness of Bichromatic Closest Pair with Jaccard Similarity. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 74:1-74:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{pagh_et_al:LIPIcs.ESA.2019.74, author = {Pagh, Rasmus and Stausholm, Nina Mesing and Thorup, Mikkel}, title = {{Hardness of Bichromatic Closest Pair with Jaccard Similarity}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {74:1--74:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.74}, URN = {urn:nbn:de:0030-drops-111951}, doi = {10.4230/LIPIcs.ESA.2019.74}, annote = {Keywords: fine-grained complexity, set similarity search, bichromatic closest pair, jaccard similarity} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
John Fearnley, Spencer Gordon, Ruta Mehta, and Rahul Savani. Unique End of Potential Line. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 56:1-56:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{fearnley_et_al:LIPIcs.ICALP.2019.56, author = {Fearnley, John and Gordon, Spencer and Mehta, Ruta and Savani, Rahul}, title = {{Unique End of Potential Line}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {56:1--56: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.56}, URN = {urn:nbn:de:0030-drops-106327}, doi = {10.4230/LIPIcs.ICALP.2019.56}, annote = {Keywords: P-matrix linear complementarity problem, unique sink orientation, contraction map, TFNP, total search problems, continuous local search} }
Feedback for Dagstuhl Publishing