var bibbase_data = {"data":"\"Loading..\"\n\n
\n\n \n\n \n\n \n \n\n \n\n \n \n\n \n\n \n
\n generated by\n \n \"bibbase.org\"\n\n \n
\n \n\n
\n\n \n\n\n
\n \n\n Excellent! Next you can\n create a new website with this list, or\n embed it in an existing web page.\n
\n\n
\n \n\n This is just a preview! If you would like to use this list on your web page\n or create a new webpage based on this,\n create a free account and upload\n the file there. Then you will be able to modify it going forward.\n
\n\n
\n \n\n

To the site owner:

\n\n

Action required! Mendeley is changing its\n API. In order to keep using Mendeley with BibBase past April\n 14th, you need to:\n

    \n
  1. renew the authorization for BibBase on Mendeley, and
    2. \n
  2. update the BibBase URL\n in your page the same way you did when you initially set up\n this page.\n
    3. \n
\n

\n\n

\n \n \n Fix it now\n

\n
\n\n
\n\n\n
\n \n \n
\n
\n  \n yes\n \n \n (15)\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 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 \"SGDPaper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 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 \"Limits paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 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 \"Quantum paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 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 \"A paper\n  \n \n\n \n \n doi\n  \n \n\n link\n  \n\n bibtex\n \n\n \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 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 \"A paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 Protecting Obfuscation against Algebraic Attacks.\n \n \n \n\n\n \n Barak, B.; Garg, S.; Kalai, Y. T.; Paneth, O.; and Sahai, A.\n\n\n \n\n\n\n In EUROCRYPT, volume 8441, of Lecture Notes in Computer Science, pages 221-238, 2014. Springer\n \n\n\n\n
\n\n\n\n \n \n \"Protecting paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@inproceedings{BarakGKPS14,\n  author    = {Boaz Barak and\n               Sanjam Garg and\n               Yael Tauman Kalai and\n               Omer Paneth and\n               Amit Sahai},\n  title     = {Protecting Obfuscation against Algebraic Attacks},\n  booktitle = {EUROCRYPT},\n  publisher = {Springer},\n  series    = {Lecture Notes in Computer Science},\n  volume    = {8441},\n  year      = {2014},\n  pages     = {221-238},\n  url_paper = {http://eprint.iacr.org/2013/631},\n  selected = {yes},\n}\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 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 \"Fractional paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 Computational complexity and information asymmetry in financial products.\n \n \n \n\n\n \n Arora, S.; Barak, B.; Brunnermeier, M.; and Ge, R.\n\n\n \n\n\n\n Commun. ACM, 54(5): 101-107. 2011.\n \n\n\n\n
\n\n\n\n \n \n \"Computational paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@article{AroraBaBrGe11,\n  author    = {Sanjeev Arora and\n               Boaz Barak and\n               Markus Brunnermeier and\n               Rong Ge},\n  title     = {Computational complexity and information asymmetry in financial\n               products},\n  journal   = {Commun. ACM},\n  volume    = {54},\n  number    = {5},\n  year      = {2011},\n  pages     = {101-107},\n   url_paper =       {http://cacm.acm.org/magazines/2011/5/107705-computational-complexity-and-information-asymmetry-in-financial-products/fulltext},\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 Subexponential Algorithms for Unique Games and Related problems.\n \n \n \n\n\n \n Arora, S.; Barak, B.; and Steurer, D.\n\n\n \n\n\n\n In Proc. of FOCS, pages 563–572, 2010. \n \n\n\n\n
\n\n\n\n \n \n \"Subexponential paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@INProceedings{AroraBaSt10,\n author = "Sanjeev Arora and Boaz Barak and David Steurer",\n title  =  "Subexponential Algorithms for Unique Games and Related problems",\n booktitle = {Proc. of FOCS},\n year = "2010",\n pages = {563--572},\n  url_paper = {https://www.boazbarak.org/Papers/ssesubexp.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 How to Compress Interactive Communication.\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 \"How paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 Merkle Puzzles are Optimal — an $O(n^2)$ attack on key exchange from a random oracle.\n \n \n \n\n\n \n Barak, B.; and Mahmoody-Ghidary, M.\n\n\n \n\n\n\n In Proceedings of CRYPTO '09, 2009. \n \n\n\n\n
\n\n\n\n \n \n \"Merkle paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@INProceedings{BarakGh09,\n  AUTHOR =       {Boaz Barak and Mohammad Mahmoody-Ghidary},\n  TITLE =        {Merkle Puzzles are Optimal --- an $O(n^2)$ attack on key exchange from a random oracle},\n  year =         {2009},\n    BOOKTITLE =      {Proceedings of CRYPTO '09},\n         url_paper =  {https://www.boazbarak.org/Papers/merkle.pdf},\n             selected = {yes},\n}\n\n
\n
\n\n\n\n
\n\n\n
\n \n\n \n \n \n \n \n\n Path-Quality Monitoring in the Presence of Adversaries.\n \n \n \n\n\n \n Goldberg, S.; Xiao, D.; Tromer, E.; Barak, B.; and Rexford, J.\n\n\n \n\n\n\n In Proceedings of SIGMETRICS 2008, 2008. \n \n\n\n\n
\n\n\n\n \n \n \"Path-Quality paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \n\n \n\n \n \n \n \n \n \n \n\n  \n \n \n\n\n\n
\n 
@InProceedings{GoldbergXiTrBaRe08,\n title = "Path-Quality Monitoring in the Presence of Adversaries",\n author = "Sharon Goldberg and David Xiao and Eran Tromer and Boaz Barak and Jennifer Rexford",\n  booktitle = "Proceedings of SIGMETRICS 2008",\n  year = "2008",\n         url_paper =  {https://www.boazbarak.org/Papers/sigfd.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 2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction.\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 Prelimninary version in STOC '06\n\n\n\n
\n\n\n\n \n \n \"2-source paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 = {Prelimninary 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 Barak, B.\n\n\n \n\n\n\n In Proceedings of FOCS '01, pages 106–115, 2001. \n See also my thesis.\n\n\n\n
\n\n\n\n \n \n \"How paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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 = {See also my thesis.},\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 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 \"On paper\n  \n \n\n \n\n link\n  \n\n bibtex\n \n\n \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
\n
\n\n\n\n\n
\n\n\n \n
\n
\n \n

Embedding in another Page

\n
\n
\n\n

\n Copy & paste any of the following snippets into an existing\n page to embed this page. For more details see the\n documention.\n

\n\n JavaScript\n (easiest)\n
\n \n <script src=\"https://bibbase.org/show?bib=www.boazbarak.org%2Fboaz.bib&jsonp=1&filter=selected:yes&group0=selected&css=https://www.boazbarak.org/bibBaseSelected.css&jsonp=1\"></script>\n \n
\n\n PHP\n
\n \n <?php\n $contents = file_get_contents(\"https://bibbase.org/show?bib=www.boazbarak.org%2Fboaz.bib&jsonp=1&filter=selected:yes&group0=selected&css=https://www.boazbarak.org/bibBaseSelected.css\");\n print_r($contents);\n ?>\n \n
\n\n iFrame\n (not recommended)\n
\n \n <iframe src=\"https://bibbase.org/show?bib=www.boazbarak.org%2Fboaz.bib&jsonp=1&filter=selected:yes&group0=selected&css=https://www.boazbarak.org/bibBaseSelected.css\"></iframe>\n \n
\n\n\n
\n
\n \n
\n
\n\n \n \n \n \n\n
\n"}; document.write(bibbase_data.data);