Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dieter van Melkebeek and Nicollas Mocelin Sdroievski. Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 17:1-17:36, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{vanmelkebeek_et_al:LIPIcs.CCC.2023.17, author = {van Melkebeek, Dieter and Mocelin Sdroievski, Nicollas}, title = {{Instance-Wise Hardness Versus Randomness Tradeoffs for Arthur-Merlin Protocols}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {17:1--17:36}, 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.17}, URN = {urn:nbn:de:0030-drops-182870}, doi = {10.4230/LIPIcs.CCC.2023.17}, annote = {Keywords: Hardness versus randomness tradeoff, Arthur-Merlin protocol, targeted hitting set generator} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Rahul Santhanam. An Algorithmic Approach to Uniform Lower Bounds. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 35:1-35:26, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{santhanam:LIPIcs.CCC.2023.35, author = {Santhanam, Rahul}, title = {{An Algorithmic Approach to Uniform Lower Bounds}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {35:1--35:26}, 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.35}, URN = {urn:nbn:de:0030-drops-183053}, doi = {10.4230/LIPIcs.CCC.2023.35}, annote = {Keywords: Probabilistic Kolmogorov complexity, sampling algorithms, uniform lower bounds} }
Published in: Dagstuhl Reports, Volume 12, Issue 9 (2023)
Markus Bläser, Valentine Kabanets, Ronen Shaltiel, and Jacobo Torán. Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371). In Dagstuhl Reports, Volume 12, Issue 9, pp. 41-59, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@Article{blaser_et_al:DagRep.12.9.41, author = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, title = {{Algebraic and Analytic Methods in Computational Complexity (Dagstuhl Seminar 22371)}}, pages = {41--59}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2023}, volume = {12}, number = {9}, editor = {Bl\"{a}ser, Markus and Kabanets, Valentine and Shaltiel, Ronen and Tor\'{a}n, Jacobo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.12.9.41}, URN = {urn:nbn:de:0030-drops-178092}, doi = {10.4230/DagRep.12.9.41}, annote = {Keywords: (de-)randomization, algebra, circuits, coding, computational complexity} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Iftach Haitner, Noam Mazor, and Jad Silbak. Incompressiblity and Next-Block Pseudoentropy. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 66:1-66:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{haitner_et_al:LIPIcs.ITCS.2023.66, author = {Haitner, Iftach and Mazor, Noam and Silbak, Jad}, title = {{Incompressiblity and Next-Block Pseudoentropy}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {66:1--66: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.66}, URN = {urn:nbn:de:0030-drops-175697}, doi = {10.4230/LIPIcs.ITCS.2023.66}, annote = {Keywords: incompressibility, next-block pseudoentropy, sparse languages} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Ronen Shaltiel and Emanuele Viola. On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 116:1-116:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{shaltiel_et_al:LIPIcs.ITCS.2022.116, author = {Shaltiel, Ronen and Viola, Emanuele}, title = {{On Hardness Assumptions Needed for "Extreme High-End" PRGs and Fast Derandomization}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {116:1--116:17}, 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.116}, URN = {urn:nbn:de:0030-drops-157122}, doi = {10.4230/LIPIcs.ITCS.2022.116}, annote = {Keywords: Complexity Theory, Derandomization, Pseudorandom generators, Black-box proofs} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Noga Ron-Zewi, Ronen Shaltiel, and Nithin Varma. Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists). In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 33:1-33:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{ronzewi_et_al:LIPIcs.ITCS.2021.33, author = {Ron-Zewi, Noga and Shaltiel, Ronen and Varma, Nithin}, title = {{Query Complexity Lower Bounds for Local List-Decoding and Hard-Core Predicates (Even for Small Rate and Huge Lists)}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {33:1--33: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.33}, URN = {urn:nbn:de:0030-drops-135724}, doi = {10.4230/LIPIcs.ITCS.2021.33}, annote = {Keywords: Local list-decoding, Hard-core predicates, Black-box reduction, Hadamard code} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Ronen Shaltiel. Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 10:1-10:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{shaltiel:LIPIcs.APPROX/RANDOM.2020.10, author = {Shaltiel, Ronen}, title = {{Is It Possible to Improve Yao’s XOR Lemma Using Reductions That Exploit the Efficiency of Their Oracle?}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {10:1--10:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-164-1}, ISSN = {1868-8969}, year = {2020}, volume = {176}, editor = {Byrka, Jaros{\l}aw and Meka, Raghu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.10}, URN = {urn:nbn:de:0030-drops-126138}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.10}, annote = {Keywords: Yao’s XOR lemma, Hardness amplification, black-box reductions} }
Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)
Fu Li and David Zuckerman. Improved Extractors for Recognizable and Algebraic Sources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 72:1-72:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{li_et_al:LIPIcs.APPROX-RANDOM.2019.72, author = {Li, Fu and Zuckerman, David}, title = {{Improved Extractors for Recognizable and Algebraic Sources}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)}, pages = {72:1--72:22}, 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.72}, URN = {urn:nbn:de:0030-drops-112873}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2019.72}, annote = {Keywords: Extractor, Pseudorandomness} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Alexander Golovnev, Rahul Ilango, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, and Avishay Tal. AC^0[p] Lower Bounds Against MCSP via the Coin Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 66:1-66:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{golovnev_et_al:LIPIcs.ICALP.2019.66, author = {Golovnev, Alexander and Ilango, Rahul and Impagliazzo, Russell and Kabanets, Valentine and Kolokolova, Antonina and Tal, Avishay}, title = {{AC^0\lbrackp\rbrack Lower Bounds Against MCSP via the Coin Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {66:1--66:15}, 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.66}, URN = {urn:nbn:de:0030-drops-106422}, doi = {10.4230/LIPIcs.ICALP.2019.66}, annote = {Keywords: Minimum Circuit Size Problem (MCSP), circuit lower bounds, AC0\lbrackp\rbrack, coin problem, hybrid argument, MKTP, biased random boolean functions} }
Published in: LIPIcs, Volume 60, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Ronen Shaltiel and Jad Silbak. Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 45:1-45:38, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{shaltiel_et_al:LIPIcs.APPROX-RANDOM.2016.45, author = {Shaltiel, Ronen and Silbak, Jad}, title = {{Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)}, pages = {45:1--45:38}, 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.45}, URN = {urn:nbn:de:0030-drops-66682}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2016.45}, annote = {Keywords: Error Correcting Codes, List Decoding, Pseudorandomness} }
Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)
Sergei Artemenko, Russell Impagliazzo, Valentine Kabanets, and Ronen Shaltiel. Pseudorandomness When the Odds are Against You. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 9:1-9:35, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016)
@InProceedings{artemenko_et_al:LIPIcs.CCC.2016.9, author = {Artemenko, Sergei and Impagliazzo, Russell and Kabanets, Valentine and Shaltiel, Ronen}, title = {{Pseudorandomness When the Odds are Against You}}, booktitle = {31st Conference on Computational Complexity (CCC 2016)}, pages = {9:1--9:35}, 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.9}, URN = {urn:nbn:de:0030-drops-58375}, doi = {10.4230/LIPIcs.CCC.2016.9}, annote = {Keywords: Derandomization, pseudorandom generator, hitting-set generator, relative error} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Benny Applebaum, Sergei Artemenko, Ronen Shaltiel, and Guang Yang. Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions (Extended Abstract). In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 582-600, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@InProceedings{applebaum_et_al:LIPIcs.CCC.2015.582, author = {Applebaum, Benny and Artemenko, Sergei and Shaltiel, Ronen and Yang, Guang}, title = {{Incompressible Functions, Relative-Error Extractors, and the Power of Nondeterministic Reductions}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {582--600}, 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.582}, URN = {urn:nbn:de:0030-drops-50567}, doi = {10.4230/LIPIcs.CCC.2015.582}, annote = {Keywords: compression, pseudorandomness, extractors, nondeterministic reductions} }
Feedback for Dagstuhl Publishing