Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Justin Holmgren and Ron Rothblum. Linear-Size Boolean Circuits for Multiselection. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 11:1-11:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{holmgren_et_al:LIPIcs.CCC.2024.11, author = {Holmgren, Justin and Rothblum, Ron}, title = {{Linear-Size Boolean Circuits for Multiselection}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {11:1--11:20}, 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.11}, URN = {urn:nbn:de:0030-drops-204070}, doi = {10.4230/LIPIcs.CCC.2024.11}, annote = {Keywords: Private Information Retrieval, Batch Selection, Boolean Circuits} }
Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Noam Mazor and Rafael Pass. Gap MCSP Is Not (Levin) NP-Complete in Obfustopia. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 36:1-36:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{mazor_et_al:LIPIcs.CCC.2024.36, author = {Mazor, Noam and Pass, Rafael}, title = {{Gap MCSP Is Not (Levin) NP-Complete in Obfustopia}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {36:1--36:21}, 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.36}, URN = {urn:nbn:de:0030-drops-204322}, doi = {10.4230/LIPIcs.CCC.2024.36}, annote = {Keywords: Kolmogorov complexity, MCSP, Levin Reduction} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Guy Goldberg. Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 74:1-74:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{goldberg:LIPIcs.ICALP.2024.74, author = {Goldberg, Guy}, title = {{Linear Relaxed Locally Decodable and Correctable Codes Do Not Need Adaptivity and Two-Sided Error}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {74:1--74: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.74}, URN = {urn:nbn:de:0030-drops-202174}, doi = {10.4230/LIPIcs.ICALP.2024.74}, annote = {Keywords: Locally decodable codes, Relaxed locally correctable codes, Relaxed locally decodable codes} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Rex Fernando, Yuval Gelles, and Ilan Komargodski. Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 46:1-46:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fernando_et_al:LIPIcs.ITCS.2024.46, author = {Fernando, Rex and Gelles, Yuval and Komargodski, Ilan}, title = {{Scalable Distributed Agreement from LWE: Byzantine Agreement, Broadcast, and Leader Election}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {46:1--46:23}, 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.46}, URN = {urn:nbn:de:0030-drops-195744}, doi = {10.4230/LIPIcs.ITCS.2024.46}, annote = {Keywords: Byzantine agreement, scalable, learning with errors} }
Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)
Yuval Gelles and Ilan Komargodski. Brief Announcement: Scalable Agreement Protocols with Optimal Optimistic Efficiency. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 42:1-42:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{gelles_et_al:LIPIcs.DISC.2023.42, author = {Gelles, Yuval and Komargodski, Ilan}, title = {{Brief Announcement: Scalable Agreement Protocols with Optimal Optimistic Efficiency}}, booktitle = {37th International Symposium on Distributed Computing (DISC 2023)}, pages = {42:1--42:6}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-301-0}, ISSN = {1868-8969}, year = {2023}, volume = {281}, editor = {Oshman, Rotem}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.42}, URN = {urn:nbn:de:0030-drops-191684}, doi = {10.4230/LIPIcs.DISC.2023.42}, annote = {Keywords: Byzantine Agreement, Consensus, Optimistic-Pessimistic, Secure Multi-Party Computation} }
Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Noam Mazor. A Lower Bound on the Share Size in Evolving Secret Sharing. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 2:1-2:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{mazor:LIPIcs.ITC.2023.2, author = {Mazor, Noam}, title = {{A Lower Bound on the Share Size in Evolving Secret Sharing}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {2:1--2:9}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.2}, URN = {urn:nbn:de:0030-drops-183300}, doi = {10.4230/LIPIcs.ITC.2023.2}, annote = {Keywords: Secret sharing, Evolving secret sharing} }
Published in: LIPIcs, Volume 267, 4th Conference on Information-Theoretic Cryptography (ITC 2023)
Cody Freitag and Ilan Komargodski. The Cost of Statistical Security in Proofs for Repeated Squaring. In 4th Conference on Information-Theoretic Cryptography (ITC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 267, pp. 4:1-4:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{freitag_et_al:LIPIcs.ITC.2023.4, author = {Freitag, Cody and Komargodski, Ilan}, title = {{The Cost of Statistical Security in Proofs for Repeated Squaring}}, booktitle = {4th Conference on Information-Theoretic Cryptography (ITC 2023)}, pages = {4:1--4:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-271-6}, ISSN = {1868-8969}, year = {2023}, volume = {267}, editor = {Chung, Kai-Min}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2023.4}, URN = {urn:nbn:de:0030-drops-183326}, doi = {10.4230/LIPIcs.ITC.2023.4}, annote = {Keywords: Cryptographic Proofs, Repeated Squaring, Lower Bounds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ilan Komargodski and Elaine Shi. Differentially Oblivious Turing Machines. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 68:1-68:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{komargodski_et_al:LIPIcs.ITCS.2021.68, author = {Komargodski, Ilan and Shi, Elaine}, title = {{Differentially Oblivious Turing Machines}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {68:1--68:19}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.68}, URN = {urn:nbn:de:0030-drops-136071}, doi = {10.4230/LIPIcs.ITCS.2021.68}, annote = {Keywords: Differential privacy, Turing machines, obliviousness} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious Parallel Tight Compaction. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{asharov_et_al:LIPIcs.ITC.2020.11, author = {Asharov, Gilad and Komargodski, Ilan and Lin, Wei-Kai and Peserico, Enoch and Shi, Elaine}, title = {{Oblivious Parallel Tight Compaction}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {11:1--11:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-151-1}, ISSN = {1868-8969}, year = {2020}, volume = {163}, editor = {Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.11}, URN = {urn:nbn:de:0030-drops-121164}, doi = {10.4230/LIPIcs.ITC.2020.11}, annote = {Keywords: Oblivious tight compaction, parallel oblivious RAM, EREW PRAM} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Tomer Grossman, Ilan Komargodski, and Moni Naor. Instance Complexity and Unlabeled Certificates in the Decision Tree Model. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 56:1-56:38, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{grossman_et_al:LIPIcs.ITCS.2020.56, author = {Grossman, Tomer and Komargodski, Ilan and Naor, Moni}, title = {{Instance Complexity and Unlabeled Certificates in the Decision Tree Model}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {56:1--56:38}, 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.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.56}, URN = {urn:nbn:de:0030-drops-117418}, doi = {10.4230/LIPIcs.ITCS.2020.56}, annote = {Keywords: decision tree complexity, instance complexity, instance optimality, query complexity, unlabeled certificates} }
Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)
Yael Tauman Kalai, Ilan Komargodski, and Ran Raz. A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols. In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, pp. 34:1-34:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{taumankalai_et_al:LIPIcs.DISC.2018.34, author = {Tauman Kalai, Yael and Komargodski, Ilan and Raz, Ran}, title = {{A Lower Bound for Adaptively-Secure Collective Coin-Flipping Protocols}}, booktitle = {32nd International Symposium on Distributed Computing (DISC 2018)}, pages = {34:1--34:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-092-7}, ISSN = {1868-8969}, year = {2018}, volume = {121}, editor = {Schmid, Ulrich and Widder, Josef}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.34}, URN = {urn:nbn:de:0030-drops-98230}, doi = {10.4230/LIPIcs.DISC.2018.34}, annote = {Keywords: Coin flipping, adaptive corruptions, byzantine faults, lower bound} }
Published in: LIPIcs, Volume 40, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
Siyao Guo and Ilan Komargodski. Negation-Limited Formulas. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 40, pp. 850-866, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{guo_et_al:LIPIcs.APPROX-RANDOM.2015.850, author = {Guo, Siyao and Komargodski, Ilan}, title = {{Negation-Limited Formulas}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)}, pages = {850--866}, 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.850}, URN = {urn:nbn:de:0030-drops-53400}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2015.850}, annote = {Keywords: Negation complexity, De Morgan formulas, Shrinkage} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Oded Goldreich, Tom Gur, and Ilan Komargodski. Strong Locally Testable Codes with Relaxed Local Decoders. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 1-41, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{goldreich_et_al:LIPIcs.CCC.2015.1, author = {Goldreich, Oded and Gur, Tom and Komargodski, Ilan}, title = {{Strong Locally Testable Codes with Relaxed Local Decoders}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {1--41}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.1}, URN = {urn:nbn:de:0030-drops-50507}, doi = {10.4230/LIPIcs.CCC.2015.1}, annote = {Keywords: Locally Testable Codes, Locally Decodable Codes, PCPs of Proximity} }