Published in: LIPIcs, Volume 265, 21st International Symposium on Experimental Algorithms (SEA 2023)
Ramtin Afshar, Michael Dillencourt, Michael T. Goodrich, and Evrim Ozel. Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors. In 21st International Symposium on Experimental Algorithms (SEA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 265, pp. 8:1-8:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{afshar_et_al:LIPIcs.SEA.2023.8, author = {Afshar, Ramtin and Dillencourt, Michael and Goodrich, Michael T. and Ozel, Evrim}, title = {{Noisy Sorting Without Searching: Data Oblivious Sorting with Comparison Errors}}, booktitle = {21st International Symposium on Experimental Algorithms (SEA 2023)}, pages = {8:1--8:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-279-2}, ISSN = {1868-8969}, year = {2023}, volume = {265}, editor = {Georgiadis, Loukas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2023.8}, URN = {urn:nbn:de:0030-drops-183585}, doi = {10.4230/LIPIcs.SEA.2023.8}, annote = {Keywords: sorting, algorithms, randomization, experimentation} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel, and Madhu Sudan. Is This Correct? Let’s Check!. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 15:1-15:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{beneliezer_et_al:LIPIcs.ITCS.2023.15, author = {Ben-Eliezer, Omri and Mikulincer, Dan and Mossel, Elchanan and Sudan, Madhu}, title = {{Is This Correct? Let’s Check!}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {15:1--15:11}, 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.15}, URN = {urn:nbn:de:0030-drops-175180}, doi = {10.4230/LIPIcs.ITCS.2023.15}, annote = {Keywords: Error Propagation, Preferential Attachment} }
Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)
Ran Cohen, Iftach Haitner, Nikolaos Makriyannis, Matan Orland, and Alex Samorodnitsky. On the Round Complexity of Randomized Byzantine Agreement. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 12:1-12:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{cohen_et_al:LIPIcs.DISC.2019.12, author = {Cohen, Ran and Haitner, Iftach and Makriyannis, Nikolaos and Orland, Matan and Samorodnitsky, Alex}, title = {{On the Round Complexity of Randomized Byzantine Agreement}}, booktitle = {33rd International Symposium on Distributed Computing (DISC 2019)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-126-9}, ISSN = {1868-8969}, year = {2019}, volume = {146}, editor = {Suomela, Jukka}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.12}, URN = {urn:nbn:de:0030-drops-113199}, doi = {10.4230/LIPIcs.DISC.2019.12}, annote = {Keywords: Byzantine agreement, lower bound, round complexity} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Yan Jin, Elchanan Mossel, and Govind Ramnarayan. Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 45:1-45:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{jin_et_al:LIPIcs.ITCS.2019.45, author = {Jin, Yan and Mossel, Elchanan and Ramnarayan, Govind}, title = {{Being Corrupt Requires Being Clever, But Detecting Corruption Doesn't}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {45:1--45:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.45}, URN = {urn:nbn:de:0030-drops-101388}, doi = {10.4230/LIPIcs.ITCS.2019.45}, annote = {Keywords: Corruption detection, PMC Model, Small Set Expansion, Hardness of Approximation} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Sampath Kannan, Elchanan Mossel, Swagato Sanyal, and Grigory Yaroslavtsev. Linear Sketching over F_2. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 8:1-8:37, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{kannan_et_al:LIPIcs.CCC.2018.8, author = {Kannan, Sampath and Mossel, Elchanan and Sanyal, Swagato and Yaroslavtsev, Grigory}, title = {{Linear Sketching over F\underline2}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {8:1--8:37}, 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.8}, URN = {urn:nbn:de:0030-drops-88819}, doi = {10.4230/LIPIcs.CCC.2018.8}, annote = {Keywords: Linear sketch, Streaming algorithms, XOR-functions, Communication complexity} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Anindya De, Elchanan Mossel, and Joe Neeman. Noise Stability Is Computable and Approximately Low-Dimensional. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 10:1-10:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{de_et_al:LIPIcs.CCC.2017.10, author = {De, Anindya and Mossel, Elchanan and Neeman, Joe}, title = {{Noise Stability Is Computable and Approximately Low-Dimensional}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {10:1--10:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-040-8}, ISSN = {1868-8969}, year = {2017}, volume = {79}, editor = {O'Donnell, Ryan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2017.10}, URN = {urn:nbn:de:0030-drops-75390}, doi = {10.4230/LIPIcs.CCC.2017.10}, annote = {Keywords: Gaussian noise stability; Plurality is stablest; Ornstein Uhlenbeck operator} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Jan Hazla, Thomas Holenstein, and Elchanan Mossel. Lower Bounds on Same-Set Inner Product in Correlated Spaces. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 34:1-34:11, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{hazla_et_al:LIPIcs.APPROX-RANDOM.2016.34, author = {Hazla, Jan and Holenstein, Thomas and Mossel, Elchanan}, title = {{Lower Bounds on Same-Set Inner Product in Correlated Spaces}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {34:1--34:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-018-7}, ISSN = {1868-8969}, year = {2016}, volume = {60}, editor = {Jansen, Klaus and Mathieu, Claire and Rolim, Jos\'{e} D. P. and Umans, Chris}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2016.34}, URN = {urn:nbn:de:0030-drops-66571}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.34}, annote = {Keywords: same set hitting, product spaces, correlation, lower bounds} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Yuval Filmus, Guy Kindler, Elchanan Mossel, and Karl Wimmer. Invariance Principle on the Slice. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 15:1-15:10, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{filmus_et_al:LIPIcs.CCC.2016.15, author = {Filmus, Yuval and Kindler, Guy and Mossel, Elchanan and Wimmer, Karl}, title = {{Invariance Principle on the Slice}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {15:1--15:10}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.15}, URN = {urn:nbn:de:0030-drops-58236}, doi = {10.4230/LIPIcs.CCC.2016.15}, annote = {Keywords: analysis of boolean functions, invariance principle, Johnson association scheme, the slice} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Yuval Filmus and Elchanan Mossel. Harmonicity and Invariance on Slices of the Boolean Cube. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 16:1-16:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{filmus_et_al:LIPIcs.CCC.2016.16, author = {Filmus, Yuval and Mossel, Elchanan}, title = {{Harmonicity and Invariance on Slices of the Boolean Cube}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {16:1--16:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-008-8}, ISSN = {1868-8969}, year = {2016}, volume = {50}, editor = {Raz, Ran}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.16}, URN = {urn:nbn:de:0030-drops-58240}, doi = {10.4230/LIPIcs.CCC.2016.16}, annote = {Keywords: analysis of boolean functions, invariance principle, Johnson association scheme, the slice} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Elchanan Mossel and Sebastien Roch. Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 931-942, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{mossel_et_al:LIPIcs.APPROX-RANDOM.2015.931, author = {Mossel, Elchanan and Roch, Sebastien}, title = {{Distance-based Species Tree Estimation: Information-Theoretic Trade-off between Number of Loci and Sequence Length under the Coalescent}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {931--942}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-89-7}, ISSN = {1868-8969}, year = {2015}, volume = {40}, editor = {Garg, Naveen and Jansen, Klaus and Rao, Anup and Rolim, Jos\'{e} D. P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2015.931}, URN = {urn:nbn:de:0030-drops-53455}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.931}, annote = {Keywords: phylogenetic reconstruction, multispecies coalescent, sequence length requirement.} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Varun Kanade, Elchanan Mossel, and Tselil Schramm. Global and Local Information in Clustering Labeled Block Models. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 779-792, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2014)
@InProceedings{kanade_et_al:LIPIcs.APPROX-RANDOM.2014.779, author = {Kanade, Varun and Mossel, Elchanan and Schramm, Tselil}, title = {{Global and Local Information in Clustering Labeled Block Models}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {779--792}, 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.779}, URN = {urn:nbn:de:0030-drops-47384}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.779}, annote = {Keywords: stochastic block models, information flow on trees} }
Feedback for Dagstuhl Publishing