Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Adam Bouland, Bill Fefferman, Soumik Ghosh, Tony Metger, Umesh Vazirani, Chenyi Zhang, and Zixin Zhou. Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 21:1-21:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bouland_et_al:LIPIcs.CCC.2024.21, author = {Bouland, Adam and Fefferman, Bill and Ghosh, Soumik and Metger, Tony and Vazirani, Umesh and Zhang, Chenyi and Zhou, Zixin}, title = {{Public-Key Pseudoentanglement and the Hardness of Learning Ground State Entanglement Structure}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {21:1--21:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.21}, URN = {urn:nbn:de:0030-drops-204175}, doi = {10.4230/LIPIcs.CCC.2024.21}, annote = {Keywords: Quantum computing, Quantum complexity theory, entanglement} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Xin Li and Yan Zhong. Two-Source and Affine Non-Malleable Extractors for Small Entropy. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 108:1-108:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.108, author = {Li, Xin and Zhong, Yan}, title = {{Two-Source and Affine Non-Malleable Extractors for Small Entropy}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {108:1--108:15}, 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.108}, URN = {urn:nbn:de:0030-drops-202512}, doi = {10.4230/LIPIcs.ICALP.2024.108}, annote = {Keywords: Randomness Extractors, Non-malleable, Two-source, Affine} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Haim Kaplan, Matthew J. Katz, Rachel Saban, and Micha Sharir. The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{kaplan_et_al:LIPIcs.ESA.2023.67, author = {Kaplan, Haim and Katz, Matthew J. and Saban, Rachel and Sharir, Micha}, title = {{The Unweighted and Weighted Reverse Shortest Path Problem for Disk Graphs}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {67:1--67:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.67}, URN = {urn:nbn:de:0030-drops-187208}, doi = {10.4230/LIPIcs.ESA.2023.67}, annote = {Keywords: Computational geometry, geometric optimization, disk graphs, BFS, Dijkstra’s algorithm, reverse shortest path} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-Optimal Erasure List-Decodable Codes. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 1:1-1:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{benaroya_et_al:LIPIcs.CCC.2020.1, author = {Ben-Aroya, Avraham and Doron, Dean and Ta-Shma, Amnon}, title = {{Near-Optimal Erasure List-Decodable Codes}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {1:1--1:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.1}, URN = {urn:nbn:de:0030-drops-125531}, doi = {10.4230/LIPIcs.CCC.2020.1}, annote = {Keywords: Dispersers, Erasure codes, List decoding, Ramsey graphs, Two-source extractors} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Avraham Ben-Aroya, Gil Cohen, Dean Doron, and Amnon Ta-Shma. Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 43:1-43:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{benaroya_et_al:LIPIcs.APPROX-RANDOM.2019.43, author = {Ben-Aroya, Avraham and Cohen, Gil and Doron, Dean and Ta-Shma, Amnon}, title = {{Two-Source Condensers with Low Error and Small Entropy Gap via Entropy-Resilient Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {43:1--43: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.43}, URN = {urn:nbn:de:0030-drops-112587}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.43}, annote = {Keywords: Condensers, Extractors, Resilient functions, Explicit constructions} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Omrit Filtser and Matthew J. Katz. Algorithms for the Discrete Fréchet Distance Under Translation. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{filtser_et_al:LIPIcs.SWAT.2018.20, author = {Filtser, Omrit and Katz, Matthew J.}, title = {{Algorithms for the Discrete Fr\'{e}chet Distance Under Translation}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {20:1--20:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.20}, URN = {urn:nbn:de:0030-drops-88466}, doi = {10.4230/LIPIcs.SWAT.2018.20}, annote = {Keywords: curve similarity, discrete Fr\'{e}chet distance, translation, algorithms, BOP} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, and Amnon Ta-Shma. A New Approach for Constructing Low-Error, Two-Source Extractors. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{benaroya_et_al:LIPIcs.CCC.2018.3, author = {Ben-Aroya, Avraham and Chattopadhyay, Eshan and Doron, Dean and Li, Xin and Ta-Shma, Amnon}, title = {{A New Approach for Constructing Low-Error, Two-Source Extractors}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {3:1--3:19}, 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.3}, URN = {urn:nbn:de:0030-drops-88877}, doi = {10.4230/LIPIcs.CCC.2018.3}, annote = {Keywords: Two-Source Extractors, Non-Malleable Extractors, Pseudorandomness, Explicit Constructions} }