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-dev.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 67, 8th Innovations in Theoretical Computer Science Conference (ITCS 2017)
Joël Alwen, Susanna F. de Rezende, Jakob Nordström, and Marc Vinyals. Cumulative Space in Black-White Pebbling and Resolution. In 8th Innovations in Theoretical Computer Science Conference (ITCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 67, pp. 38:1-38:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{alwen_et_al:LIPIcs.ITCS.2017.38, author = {Alwen, Jo\"{e}l and de Rezende, Susanna F. and Nordstr\"{o}m, Jakob and Vinyals, Marc}, title = {{Cumulative Space in Black-White Pebbling and Resolution}}, booktitle = {8th Innovations in Theoretical Computer Science Conference (ITCS 2017)}, pages = {38:1--38:21}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2017.38}, URN = {urn:nbn:de:0030-drops-81918}, doi = {10.4230/LIPIcs.ITCS.2017.38}, annote = {Keywords: pebble game, pebbling, proof complexity, space, cumulative space, clause space, resolution, parallel resolution} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Joel Alwen and Chris Peikert. Generating Shorter Bases for Hard Random Lattices. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 75-86, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{alwen_et_al:LIPIcs.STACS.2009.1832, author = {Alwen, Joel and Peikert, Chris}, title = {{Generating Shorter Bases for Hard Random Lattices}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {75--86}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1832}, URN = {urn:nbn:de:0030-drops-18327}, doi = {10.4230/LIPIcs.STACS.2009.1832}, annote = {Keywords: Lattices, Random, Short basis, Average-case hardness, Hermite normal form, Cryptography} }
Feedback for Dagstuhl Publishing