Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Zongchen Chen and Elchanan Mossel. Influence Maximization in Ising Models. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 30:1-30:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ITCS.2024.30, author = {Chen, Zongchen and Mossel, Elchanan}, title = {{Influence Maximization in Ising Models}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {30:1--30:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.30}, URN = {urn:nbn:de:0030-drops-195588}, doi = {10.4230/LIPIcs.ITCS.2024.30}, annote = {Keywords: Influence maximization, Ising model, phase transition, correlation decay} }
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 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Ishay Haviv. Approximating the Orthogonality Dimension of Graphs and Hypergraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{haviv:LIPIcs.MFCS.2019.39, author = {Haviv, Ishay}, title = {{Approximating the Orthogonality Dimension of Graphs and Hypergraphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {39:1--39:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.39}, URN = {urn:nbn:de:0030-drops-109836}, doi = {10.4230/LIPIcs.MFCS.2019.39}, annote = {Keywords: orthogonal representations of hypergraphs, orthogonality dimension, hardness of approximation, Kneser and Schrijver graphs, semidefinite programming} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Nader H. Bshouty. Almost Optimal Distribution-Free Junta Testing. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 2:1-2:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bshouty:LIPIcs.CCC.2019.2, author = {Bshouty, Nader H.}, title = {{Almost Optimal Distribution-Free Junta Testing}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {2:1--2:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.2}, URN = {urn:nbn:de:0030-drops-108249}, doi = {10.4230/LIPIcs.CCC.2019.2}, annote = {Keywords: Distribution-free property testing, k-Junta} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Amey Bhangale and Subhash Khot. UG-Hardness to NP-Hardness by Losing Half. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{bhangale_et_al:LIPIcs.CCC.2019.3, author = {Bhangale, Amey and Khot, Subhash}, title = {{UG-Hardness to NP-Hardness by Losing Half}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {3:1--3:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.3}, URN = {urn:nbn:de:0030-drops-108258}, doi = {10.4230/LIPIcs.CCC.2019.3}, annote = {Keywords: NP-hardness, Inapproximability, Unique Games Conjecture} }
Published in: LIPIcs, Volume 137, 34th Computational Complexity Conference (CCC 2019)
Kaave Hosseini, Shachar Lovett, and Grigory Yaroslavtsev. Optimality of Linear Sketching Under Modular Updates. In 34th Computational Complexity Conference (CCC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 137, pp. 13:1-13:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{hosseini_et_al:LIPIcs.CCC.2019.13, author = {Hosseini, Kaave and Lovett, Shachar and Yaroslavtsev, Grigory}, title = {{Optimality of Linear Sketching Under Modular Updates}}, booktitle = {34th Computational Complexity Conference (CCC 2019)}, pages = {13:1--13:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-116-0}, ISSN = {1868-8969}, year = {2019}, volume = {137}, editor = {Shpilka, Amir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2019.13}, URN = {urn:nbn:de:0030-drops-108355}, doi = {10.4230/LIPIcs.CCC.2019.13}, annote = {Keywords: communication complexity, linear sketching, streaming algorithm} }
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)
Victor Bapst and Amin Coja-Oghlan. Harnessing the Bethe Free Energy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 467-480, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bapst_et_al:LIPIcs.APPROX-RANDOM.2015.467, author = {Bapst, Victor and Coja-Oghlan, Amin}, title = {{Harnessing the Bethe Free Energy}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {467--480}, 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.467}, URN = {urn:nbn:de:0030-drops-53180}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.467}, annote = {Keywords: Belief Propagation, free energy, Gibbs measure, partition function} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Mark Bun and Thomas Steinke. Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 625-644, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{bun_et_al:LIPIcs.APPROX-RANDOM.2015.625, author = {Bun, Mark and Steinke, Thomas}, title = {{Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {625--644}, 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.625}, URN = {urn:nbn:de:0030-drops-53274}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.625}, annote = {Keywords: Polynomial Approximations, Pseudorandomness, Concentration, Learning Theory, Halfspaces} }
Feedback for Dagstuhl Publishing