\n \n \n
\n
\n\n \n \n \n \n \n \n Watermarks in the Sand: Impossibility of Strong Watermarking for Generative Models.\n \n \n \n \n\n\n \n Zhang, H.; Edelman, B. L.; Francati, D.; Venturi, D.; Ateniese, G.; and Barak, B.\n\n\n \n\n\n\n
arXiV, abs/2311.04378. 2023.\n
\n\n
\n\n
\n\n
\n\n \n \n Paper\n \n \n \n blog\n \n \n \n paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 15 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{DBLP:journals/corr/abs-2311-04378,\n author = {Hanlin Zhang and\n Benjamin L. Edelman and\n Danilo Francati and\n Daniele Venturi and\n Giuseppe Ateniese and\n Boaz Barak},\n title = {Watermarks in the Sand: Impossibility of Strong Watermarking for Generative\n Models},\n journal = {arXiV},\n volume = {abs/2311.04378},\n year = {2023},\n url = {https://doi.org/10.48550/arXiv.2311.04378},\n doi = {10.48550/ARXIV.2311.04378},\n eprinttype = {arXiv},\n eprint = {2311.04378},\n timestamp = {Tue, 14 Nov 2023 14:47:55 +0100},\n biburl = {https://dblp.org/rec/journals/corr/abs-2311-04378.bib},\n bibsource = {dblp computer science bibliography, https://dblp.org},\n url_blog = {https://www.harvard.edu/kempner-institute/2023/11/09/watermarking-in-the-sand/},\n url_paper = {https://arxiv.org/abs/2311.04378},\n selected = {yes}\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Scaling Data-Constrained Language Models.\n \n \n \n \n\n\n \n Muennighoff, N.; Rush, A. M.; Barak, B.; Scao, T. L.; Piktus, A.; Tazi, N.; Pyysalo, S.; Wolf, T.; and Raffel, C.\n\n\n \n\n\n\n In
Thirty-seventh Conference on Neural Information Processing Systems, 2023. \n
Outstanding Main Track Paper award, Runner-Up\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 14 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{muennighoff2023scaling,\n author = {Niklas Muennighoff and Alexander M. Rush and Boaz Barak and Teven Le Scao and Aleksandra Piktus and Nouamane Tazi and Sampo Pyysalo and Thomas Wolf and Colin Raffel},\n title = {Scaling Data-Constrained Language Models},\n booktitle = {Thirty-seventh Conference on Neural Information Processing Systems},\n year = {2023},\n url_paper = {https://arxiv.org/abs/2305.16264},\n note = {Outstanding Main Track Paper award, Runner-Up},\n selected = {yes}\n}\n\n\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n On Provable Copyright Protection for Generative Models.\n \n \n \n \n\n\n \n Vyas, N.; Kakade, S. M.; and Barak, B.\n\n\n \n\n\n\n In
International Conference on Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202, of
Proceedings of Machine Learning Research, pages 35277–35299, 2023. PMLR\n
\n\n
\n\n
\n\n
\n\n \n \n Paper\n \n \n \n paper\n \n \n \n blog\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{DBLP:conf/icml/VyasKB23,\n author = {Nikhil Vyas and\n Sham M. Kakade and\n Boaz Barak},\n title = {On Provable Copyright Protection for Generative Models},\n booktitle = {International Conference on Machine Learning, {ICML} 2023, 23-29 July\n 2023, Honolulu, Hawaii, {USA}},\n series = {Proceedings of Machine Learning Research},\n volume = {202},\n pages = {35277--35299},\n publisher = {{PMLR}},\n year = {2023},\n url = {https://proceedings.mlr.press/v202/vyas23b.html},\n timestamp = {Mon, 28 Aug 2023 17:23:09 +0200},\n biburl = {https://dblp.org/rec/conf/icml/VyasKB23.bib},\n bibsource = {dblp computer science bibliography, https://dblp.org},\n url_paper = {https://arxiv.org/abs/2302.10870},\n url_blog = {https://windowsontheory.org/2023/02/21/provable-copyright-protection-for-generative-models/},\n selected = {yes}\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Deep Double Descent: Where Bigger Models and More Data Hurt.\n \n \n \n \n\n\n \n Nakkiran, P.; Kaplun, G.; Bansal, Y.; Yang, T.; Barak, B.; and Sutskever, I.\n\n\n \n\n\n\n In
ICLR 2020, 2020. \n
Also appeared in Journal of Statistical Mechanics, 2021\n\n
\n\n
\n\n
\n\n \n \n Paper\n \n \n \n blog\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 28 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{DBLP:journals/corr/abs-1912-02292,\n author = {Preetum Nakkiran and\n Gal Kaplun and\n Yamini Bansal and\n Tristan Yang and\n Boaz Barak and\n Ilya Sutskever},\n title = {Deep Double Descent: Where Bigger Models and More Data Hurt},\n booktitle = {ICLR 2020},\n year = {2020},\n url = {http://arxiv.org/abs/1912.02292},\n archivePrefix = {arXiv},\n eprint = {1912.02292},\n timestamp = {Thu, 02 Jan 2020 18:08:18 +0100},\n biburl = {https://dblp.org/rec/bib/journals/corr/abs-1912-02292},\n bibsource = {dblp computer science bibliography, https://dblp.org},\n note = {Also appeared in Journal of Statistical Mechanics, 2021},\n url_blog = {https://windowsontheory.org/2019/12/05/deep-double-descent/},\n selected = {yes}\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n SGD on Neural Networks Learns Functions of Increasing Complexity.\n \n \n \n \n\n\n \n Nakkiran, P.; Kaplun, G.; Kalimeris, D.; Yang, T.; Edelman, B. L.; Zhang, F.; and Barak, B.\n\n\n \n\n\n\n In
NeurIPS 2019 (spotlight), volume abs/1905.11604, 2019. \n
\n\n
\n\n
\n\n
\n\n \n \n Paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 13 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{DBLP:journals/corr/abs-1905-11604,\n author = {Preetum Nakkiran and\n Gal Kaplun and\n Dimitris Kalimeris and\n Tristan Yang and\n Benjamin L. Edelman and\n Fred Zhang and\n Boaz Barak},\n title = {{SGD} on Neural Networks Learns Functions of Increasing Complexity},\n booktitle = {NeurIPS 2019 (spotlight)},\n volume = {abs/1905.11604},\n year = {2019},\n url = {http://arxiv.org/abs/1905.11604},\n archivePrefix = {arXiv},\n eprint = {1905.11604},\n timestamp = {Mon, 03 Jun 2019 13:42:33 +0200},\n biburl = {https://dblp.org/rec/bib/journals/corr/abs-1905-11604},\n bibsource = {dblp computer science bibliography, https://dblp.org},\n selected = {yes},\n}\n\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation).\n \n \n \n \n\n\n \n Barak, B.; Brakerski, Z.; Komargodski, I.; and Kothari, P.\n\n\n \n\n\n\n In
EUROCRYPT, 2018. \n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 6 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{BarakBKK17,\n AUTHOR = {Boaz Barak and Zvika Brakerski and Ilan Komargodski and Pravesh Kothari },\n TITLE = {Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)},\n booktitle = {EUROCRYPT},\n year = {2018},\n url_paper = {https://eccc.weizmann.ac.il/report/2017/060/},\n selected = {yes},\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Quantum entanglement, sum of squares, and the log rank conjecture.\n \n \n \n \n\n\n \n Barak, B.; Kothari, P.; and Steurer, D.\n\n\n \n\n\n\n In
STOC, 2017. \n
\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 12 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@inproceedings{BarakKS17,\n AUTHOR = {Boaz Barak and Pravesh Kothari and David Steurer},\n TITLE = {Quantum entanglement, sum of squares, and the log rank conjecture},\n booktitle = {STOC},\n year = {2017},\n url_paper = {https://eccc.weizmann.ac.il/report/2017/011/},\n selected = {yes},\n}\n\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem.\n \n \n \n \n\n\n \n Barak, B.; Hopkins, S. B.; Kelner, J. A.; Kothari, P. K.; Moitra, A.; and Potechin, A.\n\n\n \n\n\n\n
SIAM J. Comput., 48(2): 687–735. 2019.\n
Special issue for FOCS 2016\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n \n doi\n \n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 9 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{BarakHKKMP19,\n author = {Boaz Barak and\n Samuel B. Hopkins and\n Jonathan A. Kelner and\n Pravesh K. Kothari and\n Ankur Moitra and\n Aaron Potechin},\n title = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},\n journal = {{SIAM} J. Comput.},\n volume = {48},\n number = {2},\n pages = {687--735},\n year = {2019},\n doi = {10.1137/17M1138236},\n timestamp = {Thu, 23 May 2019 17:55:00 +0200},\n biburl = {https://dblp.org/rec/bib/journals/siamcomp/BarakHKKMP19},\n bibsource = {dblp computer science bibliography, https://dblp.org},\n url_paper = {http://eccc.hpi-web.de/report/2016/058/},\n selected = {yes},\n note = {Special issue for FOCS 2016}\n}\n\n\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n A zero-knowledge protocol for nuclear warhead verification.\n \n \n \n \n\n\n \n Glaser, A.; Barak, B.; and Goldston, R. J.\n\n\n \n\n\n\n
Nature, 510: 497-502. 2014.\n
See also article by R. Stone (Science, June 2014)\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 7 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@ARTICLE{GlaserBG14,\n author = {Glaser, Alexander and Barak, Boaz and Goldston, Robert J.},\n title = {A zero-knowledge protocol for nuclear warhead verification},\n journal = {Nature},\n year = {2014},\n volume = {510},\n pages = {497-502},\n selected = {yes},\n url_paper = {http://www.nature.com/nature/journal/v510/n7506/full/nature13457.html},\n note = {See also article by R. Stone (Science, June 2014)},\n}\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n Fractional Sylvester–Gallai theorems.\n \n \n \n \n\n\n \n Barak, B.; Dvir, Z.; Wigderson, A.; and Yehudayoff, A.\n\n\n \n\n\n\n
Proceedings of the National Academy of Sciences. 2012.\n
Journal version of STOC '11 paper ``Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes''\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{BarakDWY12,\n title={Fractional Sylvester--Gallai theorems},\n author={Barak, Boaz and Dvir, Zeev and Wigderson, Avi and Yehudayoff, Amir},\n journal={Proceedings of the National Academy of Sciences},\n year={2012},\n publisher={National Acad Sciences},\n note = {Journal version of STOC '11 paper ``Rank Bounds for Design Matrices with Applications to\nCombinatorial Geometry and Locally Correctable Codes''},\n url_paper = {http://www.cs.princeton.edu/~zdvir/papers/BDWYpnas.pdf},\n selected = {yes},\n}\n\n\n\n
\n
\n\n\n\n
\n\n\n
\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n How to Compress Interactive Communication.\n \n \n \n \n\n\n \n Barak, B.; Braverman, M.; Chen, X.; and Rao, A.\n\n\n \n\n\n\n
SIAM J. Comput., 42(3): 1327-1363. 2013.\n
Preliminary version in STOC 2010\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 2 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{BarakBCR13,\n author = {Boaz Barak and\n Mark Braverman and\n Xi Chen and\n Anup Rao},\n title = {How to Compress Interactive Communication},\n journal = {SIAM J. Comput.},\n volume = {42},\n number = {3},\n year = {2013},\n pages = {1327-1363},\n url_paper = {https://www.boazbarak.org/Papers/directsum.pdf},\n note = {Preliminary version in STOC 2010},\n selected = {yes},\n }\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n 2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction.\n \n \n \n \n\n\n \n Barak, B.; Rao, A.; Shaltiel, R.; and Wigderson, A.\n\n\n \n\n\n\n
Annals of Mathematics, 176(3): 1483–1543. 2012.\n
Preliminary version in STOC '06\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 4 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{BarakRSW12,\n title={2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction},\n author={Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi},\n journal={Annals of Mathematics},\n volume={176},\n number={3},\n pages={1483--1543},\n year={2012},\n publisher={ANNAL MATHEMATICS FINE HALL, WASHINGTON RD, PRINCETON, NJ 08544 USA},\n note = {Preliminary version in STOC '06},\n url_paper = {https://www.boazbarak.org/Papers/disperser.pdf},\n selected = {yes},\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n How to go beyond the black-box simulation barrier.\n \n \n \n \n\n\n \n Barak, B.\n\n\n \n\n\n\n In
Proceedings of FOCS '01, pages 106–115, 2001. \n
Winner, FOCS 2021 Test of Time Award\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 18 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@InProceedings{Barak01,\n author = "Boaz Barak",\n title = "How to go beyond the black-box simulation barrier",\n year = "2001",\n pages = "106--115",\n booktitle = {Proceedings of FOCS '01},\n year = {2001},\n note = {Winner, FOCS 2021 Test of Time Award},\n url_paper = {https://www.boazbarak.org/Papers/nonbb.pdf},\n selected = {yes},\n}\n\n\n
\n
\n\n\n\n
\n\n\n
\n
\n\n \n \n \n \n \n \n On the (im)possibility of obfuscating programs.\n \n \n \n \n\n\n \n Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S. P.; and Yang, K.\n\n\n \n\n\n\n
J. ACM, 59(2): 6. 2012.\n
Preliminary version in CRYPTO 2001\n\n
\n\n
\n\n
\n\n \n \n paper\n \n \n\n \n\n \n link\n \n \n\n bibtex\n \n\n \n\n \n \n \n 21 downloads\n \n \n\n \n \n \n \n \n \n \n\n \n \n \n\n\n\n
\n
@article{DBLP:journals/jacm/BarakGIRSVY12,\n author = {Boaz Barak and\n Oded Goldreich and\n Russell Impagliazzo and\n Steven Rudich and\n Amit Sahai and\n Salil P. Vadhan and\n Ke Yang},\n title = {On the (im)possibility of obfuscating programs},\n journal = {J. ACM},\n volume = {59},\n number = {2},\n year = {2012},\n pages = {6},\n note = {Preliminary version in CRYPTO 2001},\n url_paper = {https://www.boazbarak.org/Papers/obfuscate.pdf},\n selected = {yes},\n}\n\n\n\n
\n
\n\n\n\n
\n\n\n\n\n\n