Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Eshan Chattopadhyay and Jyun-Jie Liao. Hardness Against Linear Branching Programs and More. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 9:1-9:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2023.9, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Hardness Against Linear Branching Programs and More}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {9:1--9:27}, 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.9}, URN = {urn:nbn:de:0030-drops-182794}, doi = {10.4230/LIPIcs.CCC.2023.9}, annote = {Keywords: linear branching programs, circuit lower bound, sumset extractors, hitting sets} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Oded Goldreich and Avi Wigderson. Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 12:1-12:74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{goldreich_et_al:LIPIcs.CCC.2021.12, author = {Goldreich, Oded and Wigderson, Avi}, title = {{Robustly Self-Ordered Graphs: Constructions and Applications to Property Testing}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {12:1--12:74}, 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.12}, URN = {urn:nbn:de:0030-drops-142867}, doi = {10.4230/LIPIcs.CCC.2021.12}, annote = {Keywords: Asymmetric graphs, expanders, testing graph properties, two-source extractors, non-malleable extractors, coding theory, tolerant testing, random graphs} }
Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)
Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 22:1-22:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2021)
@InProceedings{cohen_et_al:LIPIcs.CCC.2021.22, author = {Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and Ta-Shma, Amnon}, title = {{Error Reduction for Weighted PRGs Against Read Once Branching Programs}}, booktitle = {36th Computational Complexity Conference (CCC 2021)}, pages = {22:1--22:17}, 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.22}, URN = {urn:nbn:de:0030-drops-142963}, doi = {10.4230/LIPIcs.CCC.2021.22}, annote = {Keywords: Pseudorandom generators, Read once branching programs, Space-bounded computation} }
Published in: LIPIcs, Volume 169, 35th Computational Complexity Conference (CCC 2020)
Eshan Chattopadhyay and Jyun-Jie Liao. Optimal Error Pseudodistributions for Read-Once Branching Programs. In 35th Computational Complexity Conference (CCC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 169, pp. 25:1-25:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{chattopadhyay_et_al:LIPIcs.CCC.2020.25, author = {Chattopadhyay, Eshan and Liao, Jyun-Jie}, title = {{Optimal Error Pseudodistributions for Read-Once Branching Programs}}, booktitle = {35th Computational Complexity Conference (CCC 2020)}, pages = {25:1--25:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-156-6}, ISSN = {1868-8969}, year = {2020}, volume = {169}, editor = {Saraf, Shubhangi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2020.25}, URN = {urn:nbn:de:0030-drops-125779}, doi = {10.4230/LIPIcs.CCC.2020.25}, annote = {Keywords: Derandomization, explicit constructions, space-bounded computation} }
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} }
Feedback for Dagstuhl Publishing