Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Shuichi Hirahara, Zhenjian Lu, and Hanlin Ren. Bounded Relativization. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 6:1-6:45, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{hirahara_et_al:LIPIcs.CCC.2023.6, author = {Hirahara, Shuichi and Lu, Zhenjian and Ren, Hanlin}, title = {{Bounded Relativization}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {6:1--6:45}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-282-2}, ISSN = {1868-8969}, year = {2023}, volume = {264}, editor = {Ta-Shma, Amnon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.6}, URN = {urn:nbn:de:0030-drops-182764}, doi = {10.4230/LIPIcs.CCC.2023.6}, annote = {Keywords: relativization, circuit lower bound, derandomization, explicit construction, pseudodeterministic algorithms, interactive proofs} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Qipeng Liu. Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 82:1-82:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{liu:LIPIcs.ITCS.2023.82, author = {Liu, Qipeng}, title = {{Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {82:1--82:18}, 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.82}, URN = {urn:nbn:de:0030-drops-175859}, doi = {10.4230/LIPIcs.ITCS.2023.82}, annote = {Keywords: cryptographic protocol, one-time memory, quantum cryptography} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Guy Goldberg and Guy N. Rothblum. Sample-Based Proofs of Proximity. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 77:1-77:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{goldberg_et_al:LIPIcs.ITCS.2022.77, author = {Goldberg, Guy and N. Rothblum, Guy}, title = {{Sample-Based Proofs of Proximity}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {77:1--77:19}, 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.77}, URN = {urn:nbn:de:0030-drops-156736}, doi = {10.4230/LIPIcs.ITCS.2022.77}, annote = {Keywords: Interactive Proof Systems, Sample-Based Access, Proofs of Proximity} }
Published in: LIPIcs, Volume 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
Sumanta Ghosh and Rohit Gurjar. Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 41:1-41:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ghosh_et_al:LIPIcs.APPROX/RANDOM.2021.41, author = {Ghosh, Sumanta and Gurjar, Rohit}, title = {{Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)}, pages = {41:1--41:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-207-5}, ISSN = {1868-8969}, year = {2021}, volume = {207}, editor = {Wootters, Mary and Sanit\`{a}, Laura}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2021.41}, URN = {urn:nbn:de:0030-drops-147342}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.41}, annote = {Keywords: Linear Matroid, Matroid Intersection, Parallel Complexity, Pseudo-deterministic NC} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Vishnu Iyer, Avishay Tal, and Michael Whitmeyer. Junta Distance Approximation with Sub-Exponential Queries. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 24:1-24:38, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{iyer_et_al:LIPIcs.CCC.2021.24, author = {Iyer, Vishnu and Tal, Avishay and Whitmeyer, Michael}, title = {{Junta Distance Approximation with Sub-Exponential Queries}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {24:1--24:38}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.24}, URN = {urn:nbn:de:0030-drops-142988}, doi = {10.4230/LIPIcs.CCC.2021.24}, annote = {Keywords: Algorithms, Complexity Theory, Fourier Analysis, Juntas, Normalized Influence, Property Testing, Tolerant Property Testing} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, and Rahul Santhanam. On the Pseudo-Deterministic Query Complexity of NP Search Problems. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 36:1-36:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.CCC.2021.36, author = {Goldwasser, Shafi and Impagliazzo, Russell and Pitassi, Toniann and Santhanam, Rahul}, title = {{On the Pseudo-Deterministic Query Complexity of NP Search Problems}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {36:1--36:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-193-1}, ISSN = {1868-8969}, year = {2021}, volume = {200}, editor = {Kabanets, Valentine}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.36}, URN = {urn:nbn:de:0030-drops-143104}, doi = {10.4230/LIPIcs.CCC.2021.36}, annote = {Keywords: Pseudo-determinism, Query complexity, Proof complexity} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Shafi Goldwasser, Guy N. Rothblum, Jonathan Shafer, and Amir Yehudayoff. Interactive Proofs for Verifying Machine Learning. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 41:1-41:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2021.41, author = {Goldwasser, Shafi and Rothblum, Guy N. and Shafer, Jonathan and Yehudayoff, Amir}, title = {{Interactive Proofs for Verifying Machine Learning}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {41:1--41: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.41}, URN = {urn:nbn:de:0030-drops-135806}, doi = {10.4230/LIPIcs.ITCS.2021.41}, annote = {Keywords: PAC learning, Fourier analysis of boolean functions, Complexity gaps, Complexity lower bounds, Goldreich-Levin algorithm, Kushilevitz-Mansour algorithm, Distribution testing} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Ofer Grossman and Justin Holmgren. Error Correcting Codes for Uncompressed Messages. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 43:1-43:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{grossman_et_al:LIPIcs.ITCS.2021.43, author = {Grossman, Ofer and Holmgren, Justin}, title = {{Error Correcting Codes for Uncompressed Messages}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {43:1--43:18}, 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.43}, URN = {urn:nbn:de:0030-drops-135828}, doi = {10.4230/LIPIcs.ITCS.2021.43}, annote = {Keywords: Coding Theory, List Decoding} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Shafi Goldwasser, Ofer Grossman, Sidhanth Mohanty, and David P. Woodruff. Pseudo-Deterministic Streaming. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 79:1-79:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2020.79, author = {Goldwasser, Shafi and Grossman, Ofer and Mohanty, Sidhanth and Woodruff, David P.}, title = {{Pseudo-Deterministic Streaming}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {79:1--79:25}, 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.79}, URN = {urn:nbn:de:0030-drops-117644}, doi = {10.4230/LIPIcs.ITCS.2020.79}, annote = {Keywords: streaming, pseudo-deterministic} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Igor Carboni Oliveira and Rahul Santhanam. Pseudo-Derandomizing Learning and Approximation. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 55:1-55:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{carbonioliveira_et_al:LIPIcs.APPROX-RANDOM.2018.55, author = {Carboni Oliveira, Igor and Santhanam, Rahul}, title = {{Pseudo-Derandomizing Learning and Approximation}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {55:1--55:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.55}, URN = {urn:nbn:de:0030-drops-94598}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.55}, annote = {Keywords: derandomization, learning, approximation, boolean circuits} }
Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)
Shafi Goldwasser, Ofer Grossman, and Dhiraj Holden. Pseudo-Deterministic Proofs. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 17:1-17:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2018.17, author = {Goldwasser, Shafi and Grossman, Ofer and Holden, Dhiraj}, title = {{Pseudo-Deterministic Proofs}}, booktitle = {9th Innovations in Theoretical Computer Science Conference (ITCS 2018)}, pages = {17:1--17:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-060-6}, ISSN = {1868-8969}, year = {2018}, volume = {94}, editor = {Karlin, Anna R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.17}, URN = {urn:nbn:de:0030-drops-83669}, doi = {10.4230/LIPIcs.ITCS.2018.17}, annote = {Keywords: Pseudo-Deterministic, Interactive Proofs} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Shafi Goldwasser and Dhiraj Holden. The Complexity of Problems in P Given Correlated Instances. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 13:1-13:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{goldwasser_et_al:LIPIcs.ITCS.2017.13, author = {Goldwasser, Shafi and Holden, Dhiraj}, title = {{The Complexity of Problems in P Given Correlated Instances}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {13:1--13:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-029-3}, ISSN = {1868-8969}, year = {2017}, volume = {67}, editor = {Papadimitriou, Christos H.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.13}, URN = {urn:nbn:de:0030-drops-81753}, doi = {10.4230/LIPIcs.ITCS.2017.13}, annote = {Keywords: Correlated instances, Longest Common Subsequence, Fine-grained complexity} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Shafi Goldwasser and Ofer Grossman. Bipartite Perfect Matching in Pseudo-Deterministic NC. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 87:1-87:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{goldwasser_et_al:LIPIcs.ICALP.2017.87, author = {Goldwasser, Shafi and Grossman, Ofer}, title = {{Bipartite Perfect Matching in Pseudo-Deterministic NC}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {87:1--87:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.87}, URN = {urn:nbn:de:0030-drops-74824}, doi = {10.4230/LIPIcs.ICALP.2017.87}, annote = {Keywords: Parallel Algorithms, Pseudo-determinism, RNC, Perfect Matching} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Shafi Goldwasser. Pseudo-deterministic Algorithms (Invited Talk). In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, p. 29, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{goldwasser:LIPIcs.STACS.2012.29, author = {Goldwasser, Shafi}, title = {{Pseudo-deterministic Algorithms}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {29--29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.29}, URN = {urn:nbn:de:0030-drops-34435}, doi = {10.4230/LIPIcs.STACS.2012.29}, annote = {Keywords: randomized algorithms, distributed computing, Monte Carlo, Las Vegas} }
Published in: Dagstuhl Seminar Proceedings, Volume 8491, Theoretical Foundations of Practical Information Security (2009)
Ran Canetti, Shafi Goldwasser, Günter Müller, and Rainer Steinwandt. 08491 Abstracts Collection – Theoretical Foundations of Practical Information Security. In Theoretical Foundations of Practical Information Security. Dagstuhl Seminar Proceedings, Volume 8491, pp. 1-16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2009)
@InProceedings{canetti_et_al:DagSemProc.08491.1, author = {Canetti, Ran and Goldwasser, Shafi and M\"{u}ller, G\"{u}nter and Steinwandt, Rainer}, title = {{08491 Abstracts Collection – Theoretical Foundations of Practical Information Security}}, booktitle = {Theoretical Foundations of Practical Information Security}, pages = {1--16}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {8491}, editor = {Ran Canetti and Shafi Goldwasser and G\"{u}nter M\"{u}ller and Rainer Steinwandt}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.08491.1}, URN = {urn:nbn:de:0030-drops-18945}, doi = {10.4230/DagSemProc.08491.1}, annote = {Keywords: Organic computing, self-organisation, design, adaptivity} }
Feedback for Dagstuhl Publishing