Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Dean Doron and Roei Tell. Derandomization with Minimal Memory Footprint. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{doron_et_al:LIPIcs.CCC.2023.11, author = {Doron, Dean and Tell, Roei}, title = {{Derandomization with Minimal Memory Footprint}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {11:1--11:15}, 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.11}, URN = {urn:nbn:de:0030-drops-182816}, doi = {10.4230/LIPIcs.CCC.2023.11}, annote = {Keywords: derandomization, space-bounded computation, catalytic space} }
Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)
Dean Doron, Amnon Ta-Shma, and Roei Tell. On Hitting-Set Generators for Polynomials That Vanish Rarely. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 7:1-7:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{doron_et_al:LIPIcs.APPROX/RANDOM.2020.7, author = {Doron, Dean and Ta-Shma, Amnon and Tell, Roei}, title = {{On Hitting-Set Generators for Polynomials That Vanish Rarely}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)}, pages = {7:1--7:23}, 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.7}, URN = {urn:nbn:de:0030-drops-126109}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.7}, annote = {Keywords: Hitting-set generators, Polynomials over finite fields, Quantified derandomization} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Igor Carboni Oliveira, Rahul Santhanam, and Roei Tell. Expander-Based Cryptography Meets Natural Proofs. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{carbonioliveira_et_al:LIPIcs.ITCS.2019.18, author = {Carboni Oliveira, Igor and Santhanam, Rahul and Tell, Roei}, title = {{Expander-Based Cryptography Meets Natural Proofs}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {18:1--18: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.18}, URN = {urn:nbn:de:0030-drops-101112}, doi = {10.4230/LIPIcs.ITCS.2019.18}, annote = {Keywords: Pseudorandom Generators, One-Way Functions, Expanders, Circuit Complexity} }
Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)
Roei Tell. Lower Bounds on Black-Box Reductions of Hitting to Density Estimation. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 58:1-58:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{tell:LIPIcs.STACS.2018.58, author = {Tell, Roei}, title = {{Lower Bounds on Black-Box Reductions of Hitting to Density Estimation}}, booktitle = {35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)}, pages = {58:1--58:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-062-0}, ISSN = {1868-8969}, year = {2018}, volume = {96}, editor = {Niedermeier, Rolf and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.58}, URN = {urn:nbn:de:0030-drops-85005}, doi = {10.4230/LIPIcs.STACS.2018.58}, annote = {Keywords: Approximate Counting, Lower Bounds, Derandomization, Parallel Algorithms, Query Complexity} }
Published in: LIPIcs, Volume 79, 32nd Computational Complexity Conference (CCC 2017)
Roei Tell. Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials. In 32nd Computational Complexity Conference (CCC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 79, pp. 13:1-13:48, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{tell:LIPIcs.CCC.2017.13, author = {Tell, Roei}, title = {{Improved Bounds for Quantified Derandomization of Constant-Depth Circuits and Polynomials}}, booktitle = {32nd Computational Complexity Conference (CCC 2017)}, pages = {13:1--13:48}, 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.13}, URN = {urn:nbn:de:0030-drops-75349}, doi = {10.4230/LIPIcs.CCC.2017.13}, annote = {Keywords: Computational complexity, derandomization, quantified derandomization, hitting-set generator, constant-depth circuits} }
Feedback for Dagstuhl Publishing