Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Gil Cohen and Tal Yankovitz. Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 8:1-8:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{cohen_et_al:LIPIcs.CCC.2024.8, author = {Cohen, Gil and Yankovitz, Tal}, title = {{Asymptotically-Good RLCCs with (log n)^(2+o(1)) Queries}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {8:1--8:16}, 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.8}, URN = {urn:nbn:de:0030-drops-204045}, doi = {10.4230/LIPIcs.CCC.2024.8}, annote = {Keywords: Relaxed locally decodable codes, Relxaed locally correctable codes, RLCC, RLDC} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, and Samson Zhou. How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 59:1-59:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{blocki_et_al:LIPIcs.APPROX/RANDOM.2023.59, author = {Blocki, Jeremiah and Grigorescu, Elena and Mukherjee, Tamalika and Zhou, Samson}, title = {{How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {59:1--59:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.59}, URN = {urn:nbn:de:0030-drops-188849}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.59}, annote = {Keywords: Differential privacy, approximation algorithms} }
Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, and Minshen Zhu. On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 14:1-14:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{block_et_al:LIPIcs.CCC.2023.14, author = {Block, Alexander R. and Blocki, Jeremiah and Cheng, Kuan and Grigorescu, Elena and Li, Xin and Zheng, Yu and Zhu, Minshen}, title = {{On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors}}, booktitle = {38th Computational Complexity Conference (CCC 2023)}, pages = {14:1--14:25}, 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.14}, URN = {urn:nbn:de:0030-drops-182847}, doi = {10.4230/LIPIcs.CCC.2023.14}, annote = {Keywords: Relaxed Locally Decodable Codes, Hamming Errors, Insdel Errors, Lower Bounds} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Jeremiah Blocki, Elena Grigorescu, and Tamalika Mukherjee. Privately Estimating Graph Parameters in Sublinear Time. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 26:1-26:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{blocki_et_al:LIPIcs.ICALP.2022.26, author = {Blocki, Jeremiah and Grigorescu, Elena and Mukherjee, Tamalika}, title = {{Privately Estimating Graph Parameters in Sublinear Time}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {26:1--26:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.26}, URN = {urn:nbn:de:0030-drops-163674}, doi = {10.4230/LIPIcs.ICALP.2022.26}, annote = {Keywords: differential privacy, sublinear time, graph algorithms} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Jeremiah Blocki, Mike Cinkoske, Seunghoon Lee, and Jin Young Son. On Explicit Constructions of Extremely Depth Robust Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 14:1-14:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{blocki_et_al:LIPIcs.STACS.2022.14, author = {Blocki, Jeremiah and Cinkoske, Mike and Lee, Seunghoon and Son, Jin Young}, title = {{On Explicit Constructions of Extremely Depth Robust Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {14:1--14:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.14}, URN = {urn:nbn:de:0030-drops-158241}, doi = {10.4230/LIPIcs.STACS.2022.14}, annote = {Keywords: Depth-Robust Graphs, Explicit Constructions, Data-Independent Memory Hard Functions, Proofs of Space and Replication} }
Published in: LIPIcs, Volume 199, 2nd Conference on Information-Theoretic Cryptography (ITC 2021)
Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. On the Security of Proofs of Sequential Work in a Post-Quantum World. In 2nd Conference on Information-Theoretic Cryptography (ITC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 199, pp. 22:1-22:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blocki_et_al:LIPIcs.ITC.2021.22, author = {Blocki, Jeremiah and Lee, Seunghoon and Zhou, Samson}, title = {{On the Security of Proofs of Sequential Work in a Post-Quantum World}}, booktitle = {2nd Conference on Information-Theoretic Cryptography (ITC 2021)}, pages = {22:1--22:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-197-9}, ISSN = {1868-8969}, year = {2021}, volume = {199}, editor = {Tessaro, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2021.22}, URN = {urn:nbn:de:0030-drops-143415}, doi = {10.4230/LIPIcs.ITC.2021.22}, annote = {Keywords: Proof of Sequential Work, Parallel Quantum Random Oracle Model, Lower Bounds} }
Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Jeremiah Blocki and Mike Cinkoske. A New Connection Between Node and Edge Depth Robust Graphs. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{blocki_et_al:LIPIcs.ITCS.2021.64, author = {Blocki, Jeremiah and Cinkoske, Mike}, title = {{A New Connection Between Node and Edge Depth Robust Graphs}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {64:1--64: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.64}, URN = {urn:nbn:de:0030-drops-136038}, doi = {10.4230/LIPIcs.ITCS.2021.64}, annote = {Keywords: Depth robust graphs, memory hard functions} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, and Minshen Zhu. Locally Decodable/Correctable Codes for Insertions and Deletions. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{block_et_al:LIPIcs.FSTTCS.2020.16, author = {Block, Alexander R. and Blocki, Jeremiah and Grigorescu, Elena and Kulkarni, Shubhang and Zhu, Minshen}, title = {{Locally Decodable/Correctable Codes for Insertions and Deletions}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {16:1--16:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.16}, URN = {urn:nbn:de:0030-drops-132577}, doi = {10.4230/LIPIcs.FSTTCS.2020.16}, annote = {Keywords: Locally decodable/correctable codes, insert-delete channel} }
Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)
Jeremiah Blocki, Shubhang Kulkarni, and Samson Zhou. On Locally Decodable Codes in Resource Bounded Channels. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 16:1-16:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blocki_et_al:LIPIcs.ITC.2020.16, author = {Blocki, Jeremiah and Kulkarni, Shubhang and Zhou, Samson}, title = {{On Locally Decodable Codes in Resource Bounded Channels}}, booktitle = {1st Conference on Information-Theoretic Cryptography (ITC 2020)}, pages = {16:1--16: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.16}, URN = {urn:nbn:de:0030-drops-121216}, doi = {10.4230/LIPIcs.ITC.2020.16}, annote = {Keywords: Locally Decodable Codes, Resource Bounded Channels} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Jeremiah Blocki, Seunghoon Lee, and Samson Zhou. Approximating Cumulative Pebbling Cost Is Unique Games Hard. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 13:1-13:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{blocki_et_al:LIPIcs.ITCS.2020.13, author = {Blocki, Jeremiah and Lee, Seunghoon and Zhou, Samson}, title = {{Approximating Cumulative Pebbling Cost Is Unique Games Hard}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {13:1--13:27}, 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.13}, URN = {urn:nbn:de:0030-drops-116983}, doi = {10.4230/LIPIcs.ITCS.2020.13}, annote = {Keywords: Cumulative Pebbling Cost, Approximation Algorithm, Unique Games Conjecture, \gamma-Extreme Depth Robust Graph, Superconcentrator, Memory-Hard Function} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Mohammad Hassan Ameri, Jeremiah Blocki, and Samson Zhou. Computationally Data-Independent Memory Hard Functions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 36:1-36:28, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{ameri_et_al:LIPIcs.ITCS.2020.36, author = {Ameri, Mohammad Hassan and Blocki, Jeremiah and Zhou, Samson}, title = {{Computationally Data-Independent Memory Hard Functions}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {36:1--36:28}, 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.36}, URN = {urn:nbn:de:0030-drops-117214}, doi = {10.4230/LIPIcs.ITCS.2020.36}, annote = {Keywords: Computationally Data-Independent Memory Hard Function, Cumulative Memory Complexity, Dynamic Pebbling Game} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, and Samson Zhou. Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 106:1-106:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{blocki_et_al:LIPIcs.ICALP.2018.106, author = {Blocki, Jeremiah and Gandikota, Venkata and Grigorescu, Elena and Zhou, Samson}, title = {{Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {106:1--106:4}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.106}, URN = {urn:nbn:de:0030-drops-91102}, doi = {10.4230/LIPIcs.ICALP.2018.106}, annote = {Keywords: Relaxed locally correctable codes, computationally bounded channels, local expanders} }
Published in: LIPIcs, Volume 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Jeremiah Blocki, Manuel Blum, Anupam Datta, and Santosh Vempala. Towards Human Computable Passwords. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 10:1-10:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{blocki_et_al:LIPIcs.ITCS.2017.10, author = {Blocki, Jeremiah and Blum, Manuel and Datta, Anupam and Vempala, Santosh}, title = {{Towards Human Computable Passwords}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {10:1--10:47}, 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.10}, URN = {urn:nbn:de:0030-drops-81847}, doi = {10.4230/LIPIcs.ITCS.2017.10}, annote = {Keywords: Passwords, Cognitive Authentication, Human Computation, Planted Constraint Satisfaction Problem, Statistical Dimension} }