Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Xi Chen, Anindya De, Chin Ho Lee, and Rocco A. Servedio. Trace Reconstruction from Local Statistical Queries. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 52:1-52:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2024.52, author = {Chen, Xi and De, Anindya and Lee, Chin Ho and Servedio, Rocco A.}, title = {{Trace Reconstruction from Local Statistical Queries}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {52:1--52:24}, 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.52}, URN = {urn:nbn:de:0030-drops-210459}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.52}, annote = {Keywords: trace reconstruction, statistical queries, algorithmic statistics} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Dean Doron, Jonathan Mosheiff, and Mary Wootters. When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 53:1-53:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2024.53, author = {Doron, Dean and Mosheiff, Jonathan and Wootters, Mary}, title = {{When Do Low-Rate Concatenated Codes Approach The Gilbert-Varshamov Bound?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {53:1--53:12}, 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.53}, URN = {urn:nbn:de:0030-drops-210467}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.53}, annote = {Keywords: Error-correcting codes, Concatenated codes, Derandomization, Gilbert-Varshamov bound} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Artur Czumaj, Guichen Gao, Shaofeng H.-C. Jiang, Robert Krauthgamer, and Pavel Veselý. Fully-Scalable MPC Algorithms for Clustering in High Dimension. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{czumaj_et_al:LIPIcs.ICALP.2024.50, author = {Czumaj, Artur and Gao, Guichen and Jiang, Shaofeng H.-C. and Krauthgamer, Robert and Vesel\'{y}, Pavel}, title = {{Fully-Scalable MPC Algorithms for Clustering in High Dimension}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {50:1--50:20}, 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.50}, URN = {urn:nbn:de:0030-drops-201938}, doi = {10.4230/LIPIcs.ICALP.2024.50}, annote = {Keywords: Massively parallel computing, high dimension, facility location, k-median, k-means} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Arya Mazumdar and Soumyabrata Pal. Support Recovery in Universal One-Bit Compressed Sensing. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 106:1-106:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{mazumdar_et_al:LIPIcs.ITCS.2022.106, author = {Mazumdar, Arya and Pal, Soumyabrata}, title = {{Support Recovery in Universal One-Bit Compressed Sensing}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {106:1--106:20}, 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.106}, URN = {urn:nbn:de:0030-drops-157028}, doi = {10.4230/LIPIcs.ITCS.2022.106}, annote = {Keywords: Superset Recovery, Approximate Support Recovery, List union-free family, Descartes’ rule of signs} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Sainyam Galhotra, Arya Mazumdar, Soumyabrata Pal, and Barna Saha. Connectivity of Random Annulus Graphs and the Geometric Block Model. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 53:1-53:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{galhotra_et_al:LIPIcs.APPROX-RANDOM.2019.53, author = {Galhotra, Sainyam and Mazumdar, Arya and Pal, Soumyabrata and Saha, Barna}, title = {{Connectivity of Random Annulus Graphs and the Geometric Block Model}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {53:1--53:23}, 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.53}, URN = {urn:nbn:de:0030-drops-112682}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.53}, annote = {Keywords: random graphs, geometric graphs, community detection, block model} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Akshay Krishnamurthy, Arya Mazumdar, Andrew McGregor, and Soumyabrata Pal. Trace Reconstruction: Generalized and Parameterized. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 68:1-68:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{krishnamurthy_et_al:LIPIcs.ESA.2019.68, author = {Krishnamurthy, Akshay and Mazumdar, Arya and McGregor, Andrew and Pal, Soumyabrata}, title = {{Trace Reconstruction: Generalized and Parameterized}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {68:1--68:25}, 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.68}, URN = {urn:nbn:de:0030-drops-111891}, doi = {10.4230/LIPIcs.ESA.2019.68}, annote = {Keywords: deletion channel, trace reconstruction, matrix reconstruction} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Amin Coja-Oghlan, Oliver Gebhard, Max Hahn-Klimroth, and Philipp Loick. Information-Theoretic and Algorithmic Thresholds for Group Testing. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 43:1-43:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{cojaoghlan_et_al:LIPIcs.ICALP.2019.43, author = {Coja-Oghlan, Amin and Gebhard, Oliver and Hahn-Klimroth, Max and Loick, Philipp}, title = {{Information-Theoretic and Algorithmic Thresholds for Group Testing}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {43:1--43: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.43}, URN = {urn:nbn:de:0030-drops-106196}, doi = {10.4230/LIPIcs.ICALP.2019.43}, annote = {Keywords: Group testing problem, phase transitions, information theory, efficient algorithms, sharp threshold, Bayesian inference} }
Published in: Dagstuhl Reports, Volume 8, Issue 3 (2018)
Po-Ling Loh, Arya Mazumdar, Dimitris Papailiopoulos, and Rüdiger Urbanke. Coding Theory for Inference, Learning and Optimization (Dagstuhl Seminar 18112). In Dagstuhl Reports, Volume 8, Issue 3, pp. 60-73, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@Article{loh_et_al:DagRep.8.3.60, author = {Loh, Po-Ling and Mazumdar, Arya and Papailiopoulos, Dimitris and Urbanke, R\"{u}diger}, title = {{Coding Theory for Inference, Learning and Optimization (Dagstuhl Seminar 18112)}}, pages = {60--73}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {8}, number = {3}, editor = {Loh, Po-Ling and Mazumdar, Arya and Papailiopoulos, Dimitris and Urbanke, R\"{u}diger}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.3.60}, URN = {urn:nbn:de:0030-drops-92977}, doi = {10.4230/DagRep.8.3.60}, annote = {Keywords: Coding theory, Distributed optimization, Machine learning, Threshold phenomena} }
Feedback for Dagstuhl Publishing