BibBase barak, b

2024 (2)

Distinguishing the Knowable from the Unknowable with Language Models. Ahdritz, G.; Qin, T.; Vyas, N.; Barak, B.; and Edelman, B. L. ICML 2024. 2024.

Distinguishing the Knowable from the Unknowable with Language Models [link]

paper link bibtex 26 downloads

@article{ahdritz2024distinguishingknowableunknowablelanguage,
      title={Distinguishing the Knowable from the Unknowable with Language Models}, 
      author={Gustaf Ahdritz and Tian Qin and Nikhil Vyas and Boaz Barak and Benjamin L. Edelman},
      year={2024},
      eprint={2402.03563},
      archivePrefix={arXiv},
      primaryClass={cs.LG},
      journal={ICML 2024},
      url_paper={https://arxiv.org/abs/2402.03563}, 
}

Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language Models. Zhang, H.; Edelman, B. L.; Francati, D.; Venturi, D.; Ateniese, G.; and Barak, B. ICML 2024, abs/2311.04378. 2024.

Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language Models [link]

Paper

blog

paper doi link bibtex 9 downloads

@article{DBLP:journals/corr/abs-2311-04378,
  author       = {Hanlin Zhang and
                  Benjamin L. Edelman and
                  Danilo Francati and
                  Daniele Venturi and
                  Giuseppe Ateniese and
                  Boaz Barak},
  title        = {Watermarks in the Sand: Impossibility of Strong Watermarking for Large Language
                  Models},
  journal      = {arXiV},
  volume       = {abs/2311.04378},
  year         = {2024},
  journal   = {ICML 2024},
  url          = {https://doi.org/10.48550/arXiv.2311.04378},
  doi          = {10.48550/ARXIV.2311.04378},
  eprinttype    = {arXiv},
  eprint       = {2311.04378},
  timestamp    = {Tue, 14 Nov 2023 14:47:55 +0100},
  biburl       = {https://dblp.org/rec/journals/corr/abs-2311-04378.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org},
  url_blog = {https://www.harvard.edu/kempner-institute/2023/11/09/watermarking-in-the-sand/},
  url_paper = {https://arxiv.org/abs/2311.04378},
  selected = {yes}
}

2023 (7)

Remote inspection of adversary-controlled environments. Tobisch, J.; Philippe, S.; Barak, B.; Kaplun, G.; Zenger, C.; Glaser, A.; Paar, C.; and Rührmair, U. Nature communications, 14(1): 6566. 2023.
link bibtex

@article{tobisch2023remote,
  title={Remote inspection of adversary-controlled environments},
  author={Tobisch, Johannes and Philippe, S{\'e}bastien and Barak, Boaz and Kaplun, Gal and Zenger, Christian and Glaser, Alexander and Paar, Christof and R{\"u}hrmair, Ulrich},
  journal={Nature communications},
  volume={14},
  number={1},
  pages={6566},
  year={2023},
  publisher={Nature Publishing Group UK London}
}

On the works of Avi Wigderson. Barak, B.; Kalai, Y.; Raz, R.; Vadhan, S.; and Vishnoi, N. K . 2023. To appear in the Abel Prize book series, Springer

paper link bibtex 5 downloads

@article{barak2023works,
  title={On the works of Avi Wigderson},
  author={Barak, Boaz and Kalai, Yael and Raz, Ran and Vadhan, Salil and Vishnoi, Nisheeth K},
  note = {To appear in the Abel Prize book series, Springer },
  url_paper ={https://arxiv.org/abs/2307.09524},
  year={2023}
}

Robust reconstruction of single cell RNA-seq data with iterative gene weight updates. Sheng, Y.; Nitzan, M.; and Barak, B. In Thirty-first Conference on Intelligent Systems for Molecular Biology, 2023.
link bibtex

@inproceedings{sheng2023robust,
  author    = {Yueqi Sheng and Mor Nitzan and Boaz Barak},
  title     = {Robust reconstruction of single cell RNA-seq data with iterative gene weight updates},
  booktitle = {Thirty-first Conference on Intelligent Systems for Molecular Biology},
  year      = {2023},
}

Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning. Vyas, N.; Morwani, D.; Zhao, R.; Kaplun, G.; Kakade, S. M.; and Barak, B. In ICML 2024, 2023.

Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning [link]

paper link bibtex 33 downloads

@inproceedings{vyas2023beyond,
  author    = {Nikhil Vyas and Depen Morwani and Rosie Zhao and Gal Kaplun and Sham M. Kakade and Boaz Barak},
  title     = {Beyond Implicit Bias: The Insignificance of SGD Noise in Online Learning},
  booktitle = {ICML 2024},
  year      = {2023},
  url_paper      = {https://arxiv.org/abs/2306.08590}
}

Scaling Data-Constrained Language Models. Muennighoff, N.; Rush, A. M.; Barak, B.; Scao, T. L.; Piktus, A.; Tazi, N.; Pyysalo, S.; Wolf, T.; and Raffel, C. In Thirty-seventh Conference on Neural Information Processing Systems, 2023. Outstanding Main Track Paper award, Runner-Up

Scaling Data-Constrained Language Models [link]

paper link bibtex 18 downloads

@inproceedings{muennighoff2023scaling,
  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},
  title     = {Scaling Data-Constrained Language Models},
  booktitle = {Thirty-seventh Conference on Neural Information Processing Systems},
  year      = {2023},
  url_paper     = {https://arxiv.org/abs/2305.16264},
  note = {Outstanding Main Track Paper award, Runner-Up},
  selected = {yes}
}

On Provable Copyright Protection for Generative Models. Vyas, N.; Kakade, S. M.; and Barak, B. 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

On Provable Copyright Protection for Generative Models [link]

Paper

paper

blog link bibtex 5 downloads

@inproceedings{DBLP:conf/icml/VyasKB23,
  author       = {Nikhil Vyas and
                  Sham M. Kakade and
                  Boaz Barak},
  title        = {On Provable Copyright Protection for Generative Models},
  booktitle    = {International Conference on Machine Learning, {ICML} 2023, 23-29 July
                  2023, Honolulu, Hawaii, {USA}},
  series       = {Proceedings of Machine Learning Research},
  volume       = {202},
  pages        = {35277--35299},
  publisher    = {{PMLR}},
  year         = {2023},
  url          = {https://proceedings.mlr.press/v202/vyas23b.html},
  timestamp    = {Mon, 28 Aug 2023 17:23:09 +0200},
  biburl       = {https://dblp.org/rec/conf/icml/VyasKB23.bib},
  bibsource    = {dblp computer science bibliography, https://dblp.org},
  url_paper     = {https://arxiv.org/abs/2302.10870},
  url_blog = {https://windowsontheory.org/2023/02/21/provable-copyright-protection-for-generative-models/},
  selected = {yes}
}

Named Tensor Notation. Chiang, D.; Rush, A. M.; and Barak, B. Transactions on Machine learning Research. 2023.

paper link bibtex 23 downloads

@article{chiang2023named,
  author    = {David Chiang and Alexander M. Rush and Boaz Barak},
  title     = {Named Tensor Notation},
  journal   = {Transactions on Machine learning Research},
  year      = {2023},
  url_paper           = {https://arxiv.org/abs/2102.13196}
}

2022 (5)

Quantum optimization of maximum independent set using Rydberg atom arrays. Ebadi, S.; Keesling, A.; Cain, M.; Wang, T. T.; Levine, H.; Bluvstein, D.; Semeghini, G.; Omran, A.; Liu, J.; Samajdar, R.; Luo, X.; Nash, B.; Gao, X.; Barak, B.; Farhi, E.; Sachdev, S.; Gemelke, N.; Zhou, L.; Choi, S.; Pichler, H.; Wang, S.; Greiner, M.; Vuletić, V.; and Lukin, M. D. Science, 376(6598): 1209-1215. 2022.

Quantum optimization of maximum independent set using Rydberg atom arrays [link]

Paper

paper doi link bibtex 10 downloads

@article{sciencequantum22,
		author = {S. Ebadi and A. Keesling and M. Cain and T. T. Wang and H. Levine and D. Bluvstein and G. Semeghini and A. Omran and J.-G. Liu and R. Samajdar and X.-Z. Luo and B. Nash and X. Gao and B. Barak and E. Farhi and S. Sachdev and N. Gemelke and L. Zhou and S. Choi and H. Pichler and S.-T. Wang and M. Greiner and V. Vuleti{\'c} and M. D. Lukin},
	doi = {10.1126/science.abo6587},
	eprint = {https://www.science.org/doi/pdf/10.1126/science.abo6587},
	journal = {Science},
	number = {6598},
	pages = {1209-1215},
	title = {Quantum optimization of maximum independent set using Rydberg atom arrays},
	url = {https://www.science.org/doi/abs/10.1126/science.abo6587},
	volume = {376},
	year = {2022},
	url_paper = {https://arxiv.org/abs/2202.09372}
}

Noisy tensor completion via the sum-of-squares hierarchy. Barak, B.; and Moitra, A. Math. Program., 193(2): 513–548. 2022. Preliminary version in COLT 2016

Noisy tensor completion via the sum-of-squares hierarchy [link]

Paper

paper doi link bibtex 33 downloads

@article{BarakMoitra22,
  author    = {Boaz Barak and
               Ankur Moitra},
  title     = {Noisy tensor completion via the sum-of-squares hierarchy},
  journal   = {Math. Program.},
  volume    = {193},
  number    = {2},
  pages     = {513--548},
  year      = {2022},
  url       = {https://doi.org/10.1007/s10107-022-01793-9},
  doi       = {10.1007/s10107-022-01793-9},
  timestamp = {Wed, 27 Jul 2022 01:00:00 +0200},
  biburl    = {https://dblp.org/rec/journals/mp/BarakM22.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  url_paper ={http://arxiv.org/abs/1501.06521},
  note = {Preliminary version in COLT 2016}
}

Deconstructing Distributions: A Pointwise Framework of Learning. Kaplun, G.; Ghosh, N.; Garg, S.; Barak, B.; and Nakkiran, P. CoRR, abs/2202.09931. 2022.

Deconstructing Distributions: A Pointwise Framework of Learning [link]

Paper link bibtex 9 downloads

@article{KaplunGGBN22,
  author    = {Gal Kaplun and
               Nikhil Ghosh and
               Saurabh Garg and
               Boaz Barak and
               Preetum Nakkiran},
  title     = {Deconstructing Distributions: {A} Pointwise Framework of Learning},
  journal   = {CoRR},
  volume    = {abs/2202.09931},
  year      = {2022},
  url       = {https://arxiv.org/abs/2202.09931},
  eprinttype = {arXiv},
  eprint    = {2202.09931},
  timestamp = {Tue, 01 Mar 2022 00:00:00 +0100},
  biburl    = {https://dblp.org/rec/journals/corr/abs-2202-09931.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit. Barak, B.; Edelman, B. L.; Goel, S.; Kakade, S. M.; Malach, E.; and Zhang, C. CoRR, abs/2207.08799. 2022.

Hidden Progress in Deep Learning: SGD Learns Parities Near the Computational Limit [link]

Paper

paper doi link bibtex 25 downloads

@article{BarakEGKMZ22,
  author    = {Boaz Barak and
               Benjamin L. Edelman and
               Surbhi Goel and
               Sham M. Kakade and
               Eran Malach and
               Cyril Zhang},
  title     = {Hidden Progress in Deep Learning: {SGD} Learns Parities Near the Computational
               Limit},
  journal   = {CoRR},
  volume    = {abs/2207.08799},
  year      = {2022},
  url       = {https://doi.org/10.48550/arXiv.2207.08799},
  doi       = {10.48550/arXiv.2207.08799},
  eprinttype = {arXiv},
  eprint    = {2207.08799},
  url_paper = {https://arxiv.org/abs/2207.08799},
  timestamp = {Tue, 19 Jul 2022 01:00:00 +0200},
  biburl    = {https://dblp.org/rec/journals/corr/abs-2207-08799.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

Classical algorithms and quantum limitations for maximum cut on high-girth graphs. Barak, B.; and Marwaha, K. In ITCS, volume 215, of LIPIcs, pages 14:1–14:21, 2022. Also presented as poster in QIP 2022

Classical algorithms and quantum limitations for maximum cut on high-girth graphs [link]

paper link bibtex 9 downloads

@inproceedings{BarakMarwaha22,
  author     = {Boaz Barak and
                Kunal Marwaha},
  title      = {Classical algorithms and quantum limitations for maximum cut on high-girth
                graphs},
  journal    = {CoRR},
  booktitle = {ITCS},
  year       = {2022},
  url_paper        = {https://arxiv.org/abs/2106.05900},
  eprinttype = {arXiv},
  eprint     = {2106.05900},
  series    = {LIPIcs},
  volume    = {215},
  pages     = {14:1--14:21},
  timestamp  = {Thu, 14 Oct 2021 09:14:50 +0200},
  biburl     = {https://dblp.org/rec/journals/corr/abs-2106-05900.bib},
  bibsource  = {dblp computer science bibliography, https://dblp.org},
  note=  {Also presented as poster in QIP 2022}
}

2021 (6)

Revisiting Model Stitching to Compare Neural Representations. Bansal, Y.; Nakkiran, P.; and Barak, B. In NeurIPS, 2021.

Revisiting Model Stitching to Compare Neural Representations [link]

paper link bibtex 4 downloads

@inproceedings{BansalNB21,
  author     = {Yamini Bansal and
                Preetum Nakkiran and
                Boaz Barak},
  title      = {Revisiting Model Stitching to Compare Neural Representations},
  journal    = {CoRR},
  booktitle = {NeurIPS},
  year       = {2021},
  url_paper        = {https://arxiv.org/abs/2106.07682},
  eprinttype = {arXiv},
  eprint     = {2106.07682},
  timestamp  = {Tue, 29 Jun 2021 16:55:04 +0200},
}

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage. Gao, X.; Kalinowski, M.; Chou, C.; Lukin, M. D.; Barak, B.; and Choi, S. CoRR, abs/2112.01657. 2021.

Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage [link]

paper link bibtex 3 downloads

@article{GaoKCLBC21,
  author     = {Xun Gao and
                Marcin Kalinowski and
                Chi{-}Ning Chou and
                Mikhail D. Lukin and
                Boaz Barak and
                Soonwon Choi},
  title      = {Limitations of Linear Cross-Entropy as a Measure for Quantum Advantage},
  journal    = {CoRR},
  volume     = {abs/2112.01657},
  year       = {2021},
  url_paper        = {https://arxiv.org/abs/2112.01657},
  eprinttype = {arXiv},
  eprint     = {2112.01657},
  timestamp  = {Wed, 08 Dec 2021 14:48:59 +0100},
  biburl     = {https://dblp.org/rec/journals/corr/abs-2112-01657.bib},
  bibsource  = {dblp computer science bibliography, https://dblp.org}
}

Playing Unique Games on Certified Small-Set Expanders. Bafna, M.; Barak, B.; Kothari, P.; Schramm, T.; and Steurer, D. STOC, abs/2006.09969. 2021.

Playing Unique Games on Certified Small-Set Expanders [link]

Paper link bibtex 18 downloads

@article{BBKSS21,
  author        = {Mitali Bafna and
               Boaz Barak and
               Pravesh Kothari and
               Tselil Schramm and
               David Steurer},
  title         = {Playing Unique Games on Certified Small-Set Expanders},
  journal       = {STOC},
  volume        = {abs/2006.09969},
  year          = {2021},
  
  url           = {https://arxiv.org/abs/2006.09969},
  archiveprefix = {arXiv},
  eprint        = {2006.09969},
  timestamp     = {Tue, 23 Jun 2020 17:57:22 +0200},
  biburl        = {https://dblp.org/rec/journals/corr/abs-2006-09969.bib},
  bibsource     = {dblp computer science bibliography, https://dblp.org}
}

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits. Barak, B.; Chou, C.; and Gao, X. In Lee, J. R., editor(s), 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185, of LIPIcs, pages 30:1–30:20, 2021. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits [link]

Paper doi link bibtex 17 downloads

@inproceedings{DBLP:conf/innovations/BarakCG21,
  author    = {Boaz Barak and
               Chi{-}Ning Chou and
               Xun Gao},
  editor    = {James R. Lee},
  title     = {Spoofing Linear Cross-Entropy Benchmarking in Shallow Quantum Circuits},
  booktitle = {12th Innovations in Theoretical Computer Science Conference, {ITCS}
               2021, January 6-8, 2021, Virtual Conference},
  series    = {LIPIcs},
  volume    = {185},
  pages     = {30:1--30:20},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2021},
  url       = {https://arxiv.org/abs/2005.02421},
  doi       = {10.4230/LIPIcs.ITCS.2021.30},
  timestamp = {Thu, 04 Feb 2021 17:31:41 +0100},
  biburl    = {https://dblp.org/rec/conf/innovations/BarakCG21.bib},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

Work with what you've got. Barak, B. Nature Physics. Feb 2021.

Paper doi link bibtex abstract 83 downloads

@article{Barak2021,
  author   = {Barak, Boaz},
  title    = {Work with what you've got},
  journal  = {Nature Physics},
  year     = {2021},
  month    = {Feb},
  day      = {04},
  abstract = {Quantum computing combines great promise with daunting challenges --- the road to devices that solve real-world problems is still long. Now, an implementation of a quantum algorithm maps the problems we want to solve to the devices we already have.},
  issn     = {1745-2481},
  doi      = {10.1038/s41567-020-01126-7},
  url      = {https://doi.org/10.1038/s41567-020-01126-7}
}

For self-supervised learning, Rationality implies generalization, provably. Bansal, Y.; Kaplun, G.; and Barak, B. In International Conference on Learning Representations, 2021.

For self-supervised learning, Rationality implies generalization, provably [link]

Paper link bibtex 43 downloads

@inproceedings{bansal2021for,
  title     = {For self-supervised learning, Rationality implies generalization, provably},
  author    = {Yamini Bansal and Gal Kaplun and Boaz Barak},
  booktitle = {International Conference on Learning Representations},
  year      = {2021},
  url           = {https://arxiv.org/abs/2010.08508},
}

2020 (4)

On Higher-Order Cryptography. Barak, B.; Crubillé, R.; and Lago, U. D. In Czumaj, A.; Dawar, A.; and Merelli, E., editor(s), 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168, of LIPIcs, pages 108:1–108:16, 2020. Schloss Dagstuhl - Leibniz-Zentrum für Informatik

Paper doi link bibtex 42 downloads

@inproceedings{DBLP:conf/icalp/BarakCL20,
  author    = {Boaz Barak and
               Rapha{\"{e}}lle Crubill{\'{e}} and
               Ugo Dal Lago},
  editor    = {Artur Czumaj and
               Anuj Dawar and
               Emanuela Merelli},
  title     = {On Higher-Order Cryptography},
  booktitle = {47th International Colloquium on Automata, Languages, and Programming,
               {ICALP} 2020, July 8-11, 2020, Saarbr{\"{u}}cken, Germany (Virtual
               Conference)},
  series    = {LIPIcs},
  volume    = {168},
  pages     = {108:1--108:16},
  publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
  year      = {2020},
  url       = {hhttps://arxiv.org/abs/2002.07218},
  doi       = {10.4230/LIPIcs.ICALP.2020.108}
  }

Physical public templates for nuclear warhead verification. Glaser, A.; Barak, B.; Kütt, M.; and Philippe, S. Science & Global Security, 28(1): 48–59. 2020.
link bibtex

@article{glaser2020physical,
  title={Physical public templates for nuclear warhead verification},
  author={Glaser, Alexander and Barak, Boaz and K{\"u}tt, Moritz and Philippe, S{\'e}bastien},
  journal={Science \& Global Security},
  volume={28},
  number={1},
  pages={48--59},
  year={2020},
  publisher={Taylor \& Francis}
}

Optimizing testing policies for detecting COVID-19 outbreaks. Yuval, J.; Nitzan, M.; Tannenbaum, N. R.; and Barak, B. arXiv preprint arXiv:2007.04827. 2020.

Optimizing testing policies for detecting COVID-19 outbreaks [link]

Paper link bibtex 8 downloads

@article{yuval2020optimizing,
  title   = {Optimizing testing policies for detecting COVID-19 outbreaks},
  author  = {Yuval, Janni and Nitzan, Mor and Tannenbaum, Neta Ravid and Barak, Boaz},
  journal = {arXiv preprint arXiv:2007.04827},
  year    = {2020},
  url = {https://arxiv.org/abs/2007.04827}
}

Deep Double Descent: Where Bigger Models and More Data Hurt. Nakkiran, P.; Kaplun, G.; Bansal, Y.; Yang, T.; Barak, B.; and Sutskever, I. In ICLR 2020, 2020. Also appeared in Journal of Statistical Mechanics, 2021

Deep Double Descent: Where Bigger Models and More Data Hurt [link]

Paper

blog link bibtex 31 downloads

@inproceedings{DBLP:journals/corr/abs-1912-02292,
  author    = {Preetum Nakkiran and
               Gal Kaplun and
               Yamini Bansal and
               Tristan Yang and
               Boaz Barak and
               Ilya Sutskever},
  title     = {Deep Double Descent: Where Bigger Models and More Data Hurt},
  booktitle = {ICLR 2020},
  year      = {2020},
  url       = {http://arxiv.org/abs/1912.02292},
  archivePrefix = {arXiv},
  eprint    = {1912.02292},
  timestamp = {Thu, 02 Jan 2020 18:08:18 +0100},
  biburl    = {https://dblp.org/rec/bib/journals/corr/abs-1912-02292},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  note = {Also appeared in Journal of Statistical Mechanics, 2021},
  url_blog = {https://windowsontheory.org/2019/12/05/deep-double-descent/},
  selected = {yes}
}

2019 (5)

Sum-of-Squares Meets Program Obfuscation, Revisited. Barak, B.; Hopkins, S. B.; Jain, A.; Kothari, P.; and Sahai, A. In EUROCRYPT 2019, pages 226–250, 2019.

Sum-of-Squares Meets Program Obfuscation, Revisited [link]

Paper doi link bibtex 25 downloads

@inproceedings{BarakHJKS19,
  author    = {Boaz Barak and
               Samuel B. Hopkins and
               Aayush Jain and
               Pravesh Kothari and
               Amit Sahai},
  title     = {Sum-of-Squares Meets Program Obfuscation, Revisited},
  booktitle = {{EUROCRYPT} 2019},
  pages     = {226--250},
  year      = {2019},
  doi       = {10.1007/978-3-030-17653-2\_8},
  timestamp = {Tue, 14 May 2019 13:49:02 +0200},
  biburl    = {https://dblp.org/rec/bib/conf/eurocrypt/BarakHJKS19},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  url  = {https://eprint.iacr.org/2018/1237}
}

SGD on Neural Networks Learns Functions of Increasing Complexity. Nakkiran, P.; Kaplun, G.; Kalimeris, D.; Yang, T.; Edelman, B. L.; Zhang, F.; and Barak, B. In NeurIPS 2019 (spotlight), volume abs/1905.11604, 2019.

SGD on Neural Networks Learns Functions of Increasing Complexity [link]

Paper link bibtex 13 downloads

@inproceedings{DBLP:journals/corr/abs-1905-11604,
  author    = {Preetum Nakkiran and
               Gal Kaplun and
               Dimitris Kalimeris and
               Tristan Yang and
               Benjamin L. Edelman and
               Fred Zhang and
               Boaz Barak},
  title     = {{SGD} on Neural Networks Learns Functions of Increasing Complexity},
  booktitle = {NeurIPS 2019 (spotlight)},
  volume    = {abs/1905.11604},
  year      = {2019},
  url       = {http://arxiv.org/abs/1905.11604},
  archivePrefix = {arXiv},
  eprint    = {1905.11604},
  timestamp = {Mon, 03 Jun 2019 13:42:33 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/corr/abs-1905-11604},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  selected = {yes},
}

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. Barak, B.; Chou, C.; Lei, Z.; Schramm, T.; and Sheng, Y. In NeurIPS 2019, 2019.

(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs [link]

Paper link bibtex 26 downloads

@inproceedings{BCLSS18,
  author    = {Boaz Barak and
               Chi{-}Ning Chou and
               Zhixian Lei and
               Tselil Schramm and
               Yueqi Sheng},
  title     = {(Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated
               Random Graphs},
  year      = {2019},
  booktitle = {NeurIPS 2019},
  url       = {http://arxiv.org/abs/1805.02349},
}

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture. Barak, B.; Kothari, P.; and Steurer, D. In ITCS 2019, 2019.

Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture [link]

Paper link bibtex 8 downloads

@inproceedings{BarakKS18,
  author    = {Boaz Barak and
               Pravesh Kothari and
               David Steurer},
  title     = {Small-Set Expansion in Shortcode Graph and the 2-to-2 Conjecture},
  booktitle   = {ITCS 2019},
  year      = {2019},
  url       = {https://eccc.weizmann.ac.il/report/2018/077},
  timestamp = {Tue, 22 May 2018 13:28:58 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/eccc/BarakKS18},
  bibsource = {dblp computer science bibliography, https://dblp.org}
}

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. Barak, B.; Hopkins, S. B.; Kelner, J. A.; Kothari, P. K.; Moitra, A.; and Potechin, A. SIAM J. Comput., 48(2): 687–735. 2019. Special issue for FOCS 2016

A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem [link]

paper doi link bibtex 9 downloads

@article{BarakHKKMP19,
  author    = {Boaz Barak and
               Samuel B. Hopkins and
               Jonathan A. Kelner and
               Pravesh K. Kothari and
               Ankur Moitra and
               Aaron Potechin},
  title     = {A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem},
  journal   = {{SIAM} J. Comput.},
  volume    = {48},
  number    = {2},
  pages     = {687--735},
  year      = {2019},
  doi       = {10.1137/17M1138236},
  timestamp = {Thu, 23 May 2019 17:55:00 +0200},
  biburl    = {https://dblp.org/rec/bib/journals/siamcomp/BarakHKKMP19},
  bibsource = {dblp computer science bibliography, https://dblp.org},
  url_paper = {http://eccc.hpi-web.de/report/2016/058/},
   selected = {yes},
  note = {Special issue for  FOCS 2016}
}

2018 (1)

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). Barak, B.; Brakerski, Z.; Komargodski, I.; and Kothari, P. In EUROCRYPT, 2018.

Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation) [link]

paper link bibtex 7 downloads

@inproceedings{BarakBKK17,
  AUTHOR =       {Boaz Barak and  Zvika Brakerski and  Ilan Komargodski and  Pravesh Kothari },
  TITLE =        {Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation)},
  booktitle = {EUROCRYPT},
  year      = {2018},
  url_paper = {https://eccc.weizmann.ac.il/report/2017/060/},
  selected = {yes},
}

2017 (2)

The Complexity of Public-Key Cryptography. Barak, B. In 2017. Tutorial/survey in honor of Oded Goldreich 60th birthday.

The Complexity of Public-Key Cryptography [link]

Paper link bibtex 15 downloads

@inproceedings{Barak17,
    author = {Boaz Barak},
    title = {The Complexity of Public-Key Cryptography},
    year = {2017},
    url = {https://eccc.weizmann.ac.il/report/2017/065/},
    note = {Tutorial/survey in honor of Oded Goldreich 60th birthday.}
}

Quantum entanglement, sum of squares, and the log rank conjecture. Barak, B.; Kothari, P.; and Steurer, D. In STOC, 2017.

Quantum entanglement, sum of squares, and the log rank conjecture [link]

paper link bibtex 13 downloads

@inproceedings{BarakKS17,
  AUTHOR =       {Boaz Barak and Pravesh Kothari and David Steurer},
  TITLE =        {Quantum entanglement, sum of squares, and the log rank conjecture},
  booktitle = {STOC},
  year      = {2017},
  url_paper = {https://eccc.weizmann.ac.il/report/2017/011/},
  selected = {yes},
}

2016 (1)

Hopes, Fears, and Software Obfuscation. Barak, B. Communications of the ACM, 59(3): 88–96. 2016.

Hopes, Fears, and Software Obfuscation [link]

paper link bibtex 7 downloads

@article{Barak16,
  author = {Boaz Barak},
  journal= {Communications of the ACM},
  title = {Hopes, Fears, and Software Obfuscation},
  volume = {59},
  number = {3},
  pages = {88--96},
  year = {2016},
  url_paper = {http://cacm.acm.org/magazines/2016/3/198855-hopes-fears-and-software-obfuscation/fulltext},
  }

2015 (4)

Designing protocols for nuclear warhead verification. Philippe, S.; Barak, B.; and Glaser, A. In Proc. 56th Annual INMM Meeting, 2015.
link bibtex

@inproceedings{BNuclear2017,
  title={Designing protocols for nuclear warhead verification},
  author={Philippe, S{\'e}bastien and Barak, Boaz and Glaser, Alexander},
  booktitle={Proc. 56th Annual INMM Meeting},
  year={2015}
}

Beating the random assignment on constraint satisfaction problems of bounded degree. Barak, B.; Moitra, A.; O'Donnell, R.; Raghavendra, P.; Regev, O.; Steurer, D.; Trevisan, L.; Vijayaraghavan, A.; Witmer, D.; and Wright, J. In RANDOM-APPROX, 2015.

Beating the random assignment on constraint satisfaction problems of bounded degree [link]

eccc link bibtex 3 downloads

@inproceedings{BarakMORRSTVWW15,
title= {Beating the random assignment on constraint satisfaction problems of bounded degree},
author = {Boaz Barak and Ankur Moitra and Ryan O'Donnell and Prasad Raghavendra and Oded Regev and David Steurer and Luca Trevisan and Aravindan Vijayaraghavan and David Witmer and John Wright },
year = {2015},
booktitle = {RANDOM-APPROX},
 url_eccc = {http://eccc.hpi-web.de/report/2015/082/},
}

Sum of Squares Lower Bounds from Pairwise Independence. Barak, B.; Chan, S. O.; and Kothari, P. In STOC, 2015.

Sum of Squares Lower Bounds from Pairwise Independence [link]

paper link bibtex 5 downloads

@inproceedings{BarakCK15,
  AUTHOR =       {Boaz Barak and Siu On Chan and Pravesh Kothari},
  booktitle = {STOC},
  TITLE =        {Sum of Squares Lower Bounds from Pairwise Independence},
  year      = {2015},
   url_paper = {http://arxiv.org/abs/1501.00734},
}

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method. Barak, B.; Kelner, J. A.; and Steurer, D. In STOC, 2015.

Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method [link]

paper link bibtex 5 downloads

@inproceedings{BarakKelnerS15b,
  AUTHOR =       {Boaz Barak and Jonathan A. Kelner and David Steurer},
  TITLE =        {Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Method},
  year      = {2015},
  booktitle = {STOC},
   url_paper = {http://arxiv.org/abs/1407.1543},
}

2014 (8)

Authenticating nuclear warheads with high confidence. Kütt, M.; Philippe, S.; Barak, B.; Glaser, A.; and Goldston, R. J In Proceedings of the 55th Annual INMM Meeting, 2014.
link bibtex

@inproceedings{BNuclear2014,
  title={Authenticating nuclear warheads with high confidence},
  author={K{\"u}tt, Moritz and Philippe, Sebastien and Barak, Boaz and Glaser, Alexander and Goldston, Robert J},
  booktitle={Proceedings of the 55th Annual INMM Meeting},
  year={2014}
}

A zero-knowledge protocol for nuclear warhead verification. Glaser, A.; Barak, B.; and Goldston, R. J. Nature, 510: 497-502. 2014. See also article by R. Stone (Science, June 2014)

A zero-knowledge protocol for nuclear warhead verification [link]

paper link bibtex 7 downloads

@ARTICLE{GlaserBG14,
  author =       {Glaser, Alexander and Barak, Boaz and Goldston, Robert J.},
  title =        {A zero-knowledge protocol for nuclear warhead verification},
  journal =      {Nature},
  year =         {2014},
  volume =       {510},
  pages =        {497-502},
  selected = {yes},
   url_paper = {http://www.nature.com/nature/journal/v510/n7506/full/nature13457.html},
   note = {See also article by R. Stone (Science, June 2014)},
}

Sum-of-squares proofs and the quest toward optimal algorithms. Barak, B.; and Steurer, D. In Proceedings of International Congress of Mathematicians (ICM), 2014.

Sum-of-squares proofs and the quest toward optimal algorithms [link]

paper link bibtex 7 downloads

@inproceedings{BarakS14,
  AUTHOR =       {Boaz Barak and David Steurer},
  TITLE =        {Sum-of-squares proofs and the quest toward optimal algorithms},
  booktitle = {Proceedings of International Congress of Mathematicians (ICM)},
  year      = {2014},
   url_paper = {http://eccc.hpi-web.de/report/2014/059/},
}

Fun and Games with Sums of Squares. Barak, B. 2014. Also appeared on the ``Windows on Theory'' blog

Fun and Games with Sums of Squares [pdf]

pdf link bibtex 5 downloads

@unpublished{Barak14,
  AUTHOR =       {Boaz Barak},
  TITLE =        {Fun and Games with Sums of Squares},
  note = {Also appeared on the ``Windows on Theory'' blog},
  year      = {2014},
   url_pdf = {https://www.boazbarak.org/Papers/SOS.pdf},
}

Rounding sum-of-squares relaxations. Barak, B.; Kelner, J. A.; and Steurer, D. In STOC, pages 31-40, 2014.

Link

paper link bibtex 13 downloads

@inproceedings{BarakKS14,
  author    = {Boaz Barak and
               Jonathan A. Kelner and
               David Steurer},
  title     = {Rounding sum-of-squares relaxations},
  booktitle = {STOC},
  year      = {2014},
  pages     = {31-40},
  ee        = {http://doi.acm.org/10.1145/2591796.2591886},
  bibsource = {DBLP, http://dblp.uni-trier.de},
  url_paper = {http://eccc.hpi-web.de/report/2014/059/},

}

Obfuscation for Evasive Functions. Barak, B.; Bitansky, N.; Canetti, R.; Kalai, Y. T.; Paneth, O.; and Sahai, A. In TCC, pages 26-51, 2014.

Obfuscation for Evasive Functions [link]

paper link bibtex 3 downloads

@inproceedings{BarakBCKPS14,
  author    = {Boaz Barak and
               Nir Bitansky and
               Ran Canetti and
               Yael Tauman Kalai and
               Omer Paneth and
               Amit Sahai},
  title     = {Obfuscation for Evasive Functions},
  booktitle = {TCC},
  year      = {2014},
  pages     = {26-51},
  bibsource = {DBLP, http://dblp.uni-trier.de},
       url_paper = {http://eprint.iacr.org/2013/668}

}

Protecting Obfuscation against Algebraic Attacks. Barak, B.; Garg, S.; Kalai, Y. T.; Paneth, O.; and Sahai, A. In EUROCRYPT, volume 8441, of Lecture Notes in Computer Science, pages 221-238, 2014. Springer

Protecting Obfuscation against Algebraic Attacks [link]

paper link bibtex 3 downloads

@inproceedings{BarakGKPS14,
  author    = {Boaz Barak and
               Sanjam Garg and
               Yael Tauman Kalai and
               Omer Paneth and
               Amit Sahai},
  title     = {Protecting Obfuscation against Algebraic Attacks},
  booktitle = {EUROCRYPT},
  publisher = {Springer},
  series    = {Lecture Notes in Computer Science},
  volume    = {8441},
  year      = {2014},
  pages     = {221-238},
  url_paper = {http://eprint.iacr.org/2013/631},
}

Structure vs. Combinatorics in Computational Complexity. Barak, B. Bulletin of the European Association for Theoretical Computer Science, 112. 2014. Survey, also posted on Windows on Theory blog.

Structure vs. Combinatorics in Computational Complexity [link]

paper

blog link bibtex 10 downloads

@article{Barak14,
  AUTHOR =       {Boaz Barak},
  TITLE =        {Structure vs. Combinatorics in Computational Complexity},
  year      = {2014},
  journal = {Bulletin of the European Association for Theoretical Computer Science},
  volume = {112},
  note = {Survey, also posted on Windows on Theory blog. },
   url_paper = {http://eccc.hpi-web.de/report/2013/182/},
   url_blog = {http://windowsontheory.org/2013/10/07/structure-vs-combinatorics-in-computational-complexity/}
}

2013 (3)

Toward a Secure Inspection System for Nuclear Warhead Verication Without Information Barrier. Glaser, A.; Barak, B.; and Goldston, R. J. 2013. Presented at 54th Annual INMM (Institute of Nuclear Materials Management) meeting
link bibtex

@unpublished{GlaserBG13,
  AUTHOR =       {Alexander Glaser and Boaz Barak and Robert J. Goldston},
  TITLE =        {Toward a Secure Inspection System for Nuclear Warhead Verication Without Information Barrier},
  note = {Presented at 54th Annual INMM (Institute of Nuclear Materials Management) meeting},
  year      = {2013},
}

Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013. Barak, B.; Kindler, G.; and Steurer, D. In Kleinberg, R. D., editor(s), ITCS, pages 197-214, 2013. ACM

Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013 [pdf]

paper link bibtex 3 downloads

@inproceedings{BarakKS13,
  author    = {Boaz Barak and
               Guy Kindler and
               David Steurer},
  title     = {On the optimality of semidefinite relaxations for average-case
               and generalized constraint satisfaction},
  booktitle = {ITCS},
  year      = {2013},
  pages     = {197-214},
  editor    = {Robert D. Kleinberg},
  title     = {Innovations in Theoretical Computer Science, ITCS '13, Berkeley,
               CA, USA, January 9-12, 2013},
  booktitle = {ITCS},
  publisher = {ACM},
  year      = {2013},
  isbn      = {978-1-4503-1859-4},
   url_paper = {https://www.boazbarak.org/Papers/sdpopt.pdf},
}

How to Compress Interactive Communication. Barak, B.; Braverman, M.; Chen, X.; and Rao, A. SIAM J. Comput., 42(3): 1327-1363. 2013. Preliminary version in STOC 2010

How to Compress Interactive Communication [pdf]

paper link bibtex 2 downloads

@article{BarakBCR13,
  author    = {Boaz Barak and
               Mark Braverman and
               Xi Chen and
               Anup Rao},
  title     = {How to Compress Interactive Communication},
  journal   = {SIAM J. Comput.},
  volume    = {42},
  number    = {3},
  year      = {2013},
  pages     = {1327-1363},
    url_paper = {https://www.boazbarak.org/Papers/directsum.pdf},
  note = {Preliminary version in STOC 2010},
  selected = {yes},
 }

2012 (7)

Truth vs. Proof in Computational Complexity. Barak, B. Bulletin of the European Association for Theoretical Computer Science, (108). October 2012. Appeared in Logic in Computer Science column. Also posted in Windows on theory blog

Truth vs. Proof in Computational Complexity [pdf]

paper

Truth vs. Proof in Computational Complexity [link]

blog link bibtex 7 downloads

@ARTICLE{Barak12,
  AUTHOR =       {Boaz Barak},
  TITLE =        {Truth vs. Proof in Computational Complexity},
  JOURNAL =      {Bulletin of the European Association for Theoretical Computer Science},
  YEAR =         {2012},
  number =       {108},
  month =        {October},
  note =         {Appeared in Logic in Computer Science column. Also posted in Windows on theory blog},
   url_paper = {https://www.boazbarak.org/Papers/truth-proof.pdf},
   url_blog = {http://windowsontheory.org/2012/07/31/truth-vs-proof-the-unique-games-conjecture-and-feiges-hypothesis/},
}

A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol. Glaser, A.; Barak, B.; and Goldston, R. J. 2012. Presented at 53rd Annual INMM (Institute of Nuclear Materials Management) meeting

A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol [pdf]

paper

A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol [link]

powerpoint link bibtex 6 downloads

@unpublished{GlaserBG12,
  AUTHOR =       {Alexander Glaser and Boaz Barak and Robert J. Goldston},
  TITLE =        {A New Approach to Nuclear Warhead Verification Using a Zero-Knowledge Protocol},
  note = {Presented at 53rd Annual INMM (Institute of Nuclear Materials Management) meeting},
  year      = {2012},
   url_paper = {https://www.boazbarak.org/Papers/nuclear-zk.pdf},
   url_powerpoint = {https://www.boazbarak.org/Papers/nuclear-zk.ppsx},
}

Fractional Sylvester–Gallai theorems. Barak, B.; Dvir, Z.; Wigderson, A.; and Yehudayoff, A. Proceedings of the National Academy of Sciences. 2012. Journal version of STOC '11 paper ``Rank Bounds for Design Matrices with Applications to Combinatorial Geometry and Locally Correctable Codes''

Fractional Sylvester–Gallai theorems [pdf]

paper link bibtex 4 downloads

@article{BarakDWY12,
  title={Fractional Sylvester--Gallai theorems},
  author={Barak, Boaz and Dvir, Zeev and Wigderson, Avi and Yehudayoff, Amir},
  journal={Proceedings of the National Academy of Sciences},
  year={2012},
  publisher={National Acad Sciences},
  note = {Journal version of STOC '11 paper ``Rank Bounds for Design Matrices  with Applications  to
Combinatorial Geometry and Locally Correctable Codes''},
   url_paper = {http://www.cs.princeton.edu/~zdvir/papers/BDWYpnas.pdf},
   selected = {yes},
}

Making the long code shorter. Barak, B.; Gopalan, P.; Håstad, J.; Meka, R.; and Raghavendra, P. In FOCS, 2012.

eccc link bibtex 1 download

@inproceedings{BarakGHMRS12,
  AUTHOR =       {Boaz Barak and Parikshit Gopalan and Johan H{\aa}stad and Raghu Meka and Prasad Raghavendra},
  TITLE =        {Making the Long Code Shorter},
  title     = {Making the long code shorter},
  booktitle = {FOCS},
  year      = {2012},
   url_eccc = {http://eccc.hpi-web.de/report/2011/142},
}

Hypercontractivity, sum-of-squares proofs, and their applications. Barak, B.; Brandão, F. G. S. L.; Harrow, A. W.; Kelner, J. A.; Steurer, D.; and Zhou, Y. In STOC, pages 307-326, 2012.

Hypercontractivity, sum-of-squares proofs, and their applications [link]

arxiv link bibtex 10 downloads

@inproceedings{BarakBHKSZ12,
  author    = {Boaz Barak and
               Fernando G. S. L. Brand{\~a}o and
               Aram Wettroth Harrow and
               Jonathan A. Kelner and
               David Steurer and
               Yuan Zhou},
  title     = {Hypercontractivity, sum-of-squares proofs, and their applications},
  booktitle = {STOC},
  year      = {2012},
  pages     = {307-326},
   url_arxiv = {http://arxiv.org/pdf/1205.4484v1},
}

2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction. Barak, B.; Rao, A.; Shaltiel, R.; and Wigderson, A. Annals of Mathematics, 176(3): 1483–1543. 2012. Preliminary version in STOC '06
$2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction [pdf]$ paper link bibtex 5 downloads

@article{BarakRSW12,
  title={2-source dispersers for $n^{o(1)}$ entropy, and Ramsey graphs beating the Frankl-Wilson construction},
  author={Barak, Boaz and Rao, Anup and Shaltiel, Ronen and Wigderson, Avi},
  journal={Annals of Mathematics},
  volume={176},
  number={3},
  pages={1483--1543},
  year={2012},
  publisher={ANNAL MATHEMATICS FINE HALL, WASHINGTON RD, PRINCETON, NJ 08544 USA},
  note = {Preliminary version in STOC '06},
   url_paper =  {https://www.boazbarak.org/Papers/disperser.pdf},
   selected = {yes},
}

On the (im)possibility of obfuscating programs. Barak, B.; Goldreich, O.; Impagliazzo, R.; Rudich, S.; Sahai, A.; Vadhan, S. P.; and Yang, K. J. ACM, 59(2): 6. 2012. Preliminary version in CRYPTO 2001

On the (im)possibility of obfuscating programs [pdf]

paper link bibtex 22 downloads

@article{DBLP:journals/jacm/BarakGIRSVY12,
  author    = {Boaz Barak and
               Oded Goldreich and
               Russell Impagliazzo and
               Steven Rudich and
               Amit Sahai and
               Salil P. Vadhan and
               Ke Yang},
  title     = {On the (im)possibility of obfuscating programs},
  journal   = {J. ACM},
  volume    = {59},
  number    = {2},
  year      = {2012},
  pages     = {6},
  note =      {Preliminary version in CRYPTO 2001},
    url_paper = {https://www.boazbarak.org/Papers/obfuscate.pdf},
  selected = {yes},
}

2011 (4)

Rounding Semidefinite Programming Hierarchies via Global Correlation. Barak, B.; Raghavendra, P.; and Steurer, D. In FOCS, pages 472-481, 2011.

Link

arxiv link bibtex 9 downloads

@inproceedings{BarakRS11,
  author    = {Boaz Barak and
               Prasad Raghavendra and
               David Steurer},
  title     = {Rounding Semidefinite Programming Hierarchies via Global
               Correlation},
  booktitle = {FOCS},
  year      = {2011},
  pages     = {472-481},
  ee        = {http://dx.doi.org/10.1109/FOCS.2011.95},
   url_arxiv = {http://arxiv.org/pdf/1104.4680},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Leftover Hash Lemma, Revisited. Barak, B.; Dodis, Y.; Krawczyk, H.; Pereira, O.; Pietrzak, K.; Standaert, F.; and Yu, Y. In CRYPTO, 2011. According to the New Yorker, this was one of the more obscure titles in the CRYPTO '11 conference, see highlighted text in 4th page linked below

paper

new yorker link bibtex 2 downloads

@inproceedings{BarakDKPPSY11,
    author = {Boaz Barak and Yevgeniy Dodis and Hugo Krawczyk and Olivier Pereira and Krzysztof Pietrzak and Francois-Xavier Standaert and Yu Yu},
    title = {Leftover Hash Lemma, Revisited},
    booktitle = {CRYPTO},
    year = {2011},
     url_paper = {http://eprint.iacr.org/2011/088.pdf},
    note = {According to the New Yorker, this was one of the more obscure titles in the CRYPTO '11 conference, see highlighted text in 4th page linked below},
    url_New_Yorker = {http://www.cs.nyu.edu/~dodis/ps/lhl-newyorker-oct-2011.pdf},
}

Computational complexity and information asymmetry in financial products. Arora, S.; Barak, B.; Brunnermeier, M.; and Ge, R. Commun. ACM, 54(5): 101-107. 2011.

Computational complexity and information asymmetry in financial products [link]

paper link bibtex 10 downloads

@article{AroraBaBrGe11,
  author    = {Sanjeev Arora and
               Boaz Barak and
               Markus Brunnermeier and
               Rong Ge},
  title     = {Computational complexity and information asymmetry in financial
               products},
  journal   = {Commun. ACM},
  volume    = {54},
  number    = {5},
  year      = {2011},
  pages     = {101-107},
   url_paper =       {http://cacm.acm.org/magazines/2011/5/107705-computational-complexity-and-information-asymmetry-in-financial-products/fulltext},
   selected = {yes},
}

Subsampling Mathematical Programs and Average-Case Complexity. Barak, B.; Hardt, M.; Holenstein, T.; and Steurer, D. In SODA, 2011.

Subsampling Mathematical Programs and Average-Case Complexity [pdf]

paper link bibtex 4 downloads

@Inproceedings{BarakHaHoSt11,
 author = "Boaz Barak and Moritz Hardt and Thomas Holenstein and David Steurer",
 title  =  "Subsampling Mathematical Programs and Average-Case Complexity",
 year = "2011",
 booktitle = "SODA",
  url_paper = {https://www.boazbarak.org/Papers/propsdp.pdf},
 }

2010 (4)

Subexponential Algorithms for Unique Games and Related problems. Arora, S.; Barak, B.; and Steurer, D. In Proc. of FOCS, pages 563–572, 2010.

Subexponential Algorithms for Unique Games and Related problems [pdf]

paper link bibtex 6 downloads

@INProceedings{AroraBaSt10,
 author = "Sanjeev Arora and Boaz Barak and David Steurer",
 title  =  "Subexponential Algorithms for Unique Games and Related problems",
 booktitle = {Proc. of FOCS},
 year = "2010",
 pages = {563--572},
  url_paper = {https://www.boazbarak.org/Papers/ssesubexp.pdf},
  selected = {yes},
 }

Public Key Cryptography from Different Assumptions. Applebaum, B.; Barak, B.; and Wigderson, A. In Proc. of STOC, 2010. Preliminary version as cryptology eprint report 2008/335 by Barak and Wigderson

Public Key Cryptography from Different Assumptions [pdf]

paper link bibtex 7 downloads

@INProceedings{ApplebaumBaWi10,
    AUTHOR = {Benny Applebaum  and Boaz Barak and Avi Wigderson},
    TITLE =  {Public Key Cryptography from Different Assumptions},
    YEAR  =  {2010},
    booktitle = {Proc. of STOC},
     url_paper =    {https://www.boazbarak.org/Papers/ncpkcFull2.pdf},
    note =   {Preliminary version as cryptology eprint report 2008/335 by Barak and Wigderson}
}

Bounded Key-Dependent Message Security. Barak, B.; Haitner, I.; Hofheinz, D.; and Ishai, Y. In EUROCRYPT, 2010.

Bounded Key-Dependent Message Security [pdf]

paper link bibtex

@InProceedings{BarakHaHoIs10,
 author = "Boaz Barak and Iftach Haitner and Dennis Hofheinz and Yuval Ishai",
 title  =  "Bounded Key-Dependent Message Security",
 year = "2010",
 booktitle = "EUROCRYPT",
  url_paper = {   url_paper = {http://eprint.iacr.org/2009/511.pdf}},
 }

Computational Complexity and Information Asymmetry in Financial Products. Arora, S.; Barak, B.; Brunnermeier, M.; and Ge, R. In Innovations in Computer Science (ICS) conference, 2010.

Computational Complexity and Information Asymmetry in Financial Products [pdf]

paper link bibtex 2 downloads

@InProceedings{AroraBaBrGe10,
 author = "Sanjeev Arora and Boaz Barak and Markus Brunnermeier and Rong Ge",
 title  =  "Computational Complexity and Information Asymmetry in Financial Products",
 year = "2010",
  url_paper = {https://www.boazbarak.org/Papers/derivative.pdf},
 booktitle = "Innovations in Computer Science (ICS) conference",
 }

2009 (3)

Strong Parallel Repetition Theorem for Free Projection Games. Barak, B.; Rao, A.; Raz, R.; Rosen, R.; and Shaltiel, R. In Proceedings RANDOM 2009, pages 365, 2009. Springer

Strong Parallel Repetition Theorem for Free Projection Games [pdf]

paper link bibtex

@InProceedings{BarakRaRaRoSh09,
  title={Strong Parallel Repetition Theorem for Free Projection Games},
  author={Boaz Barak and Anup Rao and Ran Raz and Ricky Rosen and Ronen Shaltiel},
  booktitle={Proceedings RANDOM 2009},
  pages={365},
  year={2009},
  organization={Springer},
    url_paper = {https://www.boazbarak.org/Papers/freegames1.pdf},
}

The Uniform Hardcore Lemma via Approximate Bregman Projections. Barak, B.; Hardt, M.; and Kale, S. In Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA), 2009.

The Uniform Hardcore Lemma via Approximate Bregman Projections [pdf]

paper link bibtex

@InProceedings{BarakHaKa09,
 author = "Boaz Barak and Moritz Hardt and Satyen Kale",
 title  =  "The Uniform Hardcore Lemma via Approximate Bregman Projections",
 booktitle = "Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA)",
 year = "2009",
  url_paper = {https://www.boazbarak.org/Papers/hardcore.pdf},
 }

Merkle Puzzles are Optimal — an $O(n^2)$ attack on key exchange from a random oracle. Barak, B.; and Mahmoody-Ghidary, M. In Proceedings of CRYPTO '09, 2009.

Merkle Puzzles are Optimal — an $O(n^2)$ attack on key exchange from a random oracle [pdf]

paper link bibtex 5 downloads

@INProceedings{BarakGh09,
  AUTHOR =       {Boaz Barak and Mohammad Mahmoody-Ghidary},
  TITLE =        {Merkle Puzzles are Optimal --- an $O(n^2)$ attack on key exchange from a random oracle},
  year =         {2009},
    BOOKTITLE =      {Proceedings of CRYPTO '09},
         url_paper =  {https://www.boazbarak.org/Papers/merkle.pdf},
}

2008 (5)

Rounding Parallel Repetitions of Unique Games. Barak, B.; Hardt, M.; Haviv, I.; Rao, A.; Regev, O.; and Steurer, D. In Proceedings of 49th FOCS, 2008.

Rounding Parallel Repetitions of Unique Games [pdf]

paper link bibtex 6 downloads

@INProceedings{BarakHaHaRaReSt08,
  AUTHOR =       {Boaz Barak and Moriz Hardt and Ishay Haviv and Anup Rao and Oded Regev and David Steurer},
  TITLE =        {Rounding Parallel Repetitions of Unique Games},
  BOOKTITLE =      {Proceedings of 49th FOCS},
  YEAR =         {2008},
       url_paper =    {https://www.boazbarak.org/Papers/roundpar.pdf},
}

On Basing Lower-Bounds for Learning on Worst-Case Assumptions. Applebaum, B.; Barak, B.; and Xiao, D. In Proceedings of 49th FOCS, 2008.

On Basing Lower-Bounds for Learning on Worst-Case Assumptions [pdf]

paper link bibtex 7 downloads

@INProceedings{ApplebaumBaXi08,
  AUTHOR = {Benny Applebaum and Boaz Barak and David Xiao},
  TITLE = {On Basing Lower-Bounds for Learning on Worst-Case Assumptions},
  BOOKTITLE =      {Proceedings of 49th FOCS},
  YEAR =         {2008},
         url_paper =    {https://www.boazbarak.org/Papers/ABX08full.pdf},
}

Protocols and Lower Bounds for Failure Localization in the Internet. Barak, B.; Goldberg, S.; and Xiao, D. In Proceedings of Eurocrypt 2008, 2008.

Protocols and Lower Bounds for Failure Localization in the Internet [pdf]

paper link bibtex 1 download

@INProceedings{BarakGoXi08,
  AUTHOR =       {Boaz Barak and Sharon Goldberg and David Xiao},
  TITLE =        {Protocols and Lower Bounds for Failure Localization in the Internet},
  BOOKTITLE =    {Proceedings of Eurocrypt 2008},
  YEAR =         {2008},
       url_paper =  {https://www.boazbarak.org/Papers/eurofl.pdf},
}

Path-Quality Monitoring in the Presence of Adversaries. Goldberg, S.; Xiao, D.; Tromer, E.; Barak, B.; and Rexford, J. In Proceedings of SIGMETRICS 2008, 2008.

Path-Quality Monitoring in the Presence of Adversaries [pdf]

paper link bibtex 1 download

@InProceedings{GoldbergXiTrBaRe08,
 title = "Path-Quality Monitoring in the Presence of Adversaries",
 author = "Sharon Goldberg and David Xiao and Eran Tromer and Boaz Barak and Jennifer Rexford",
  booktitle = "Proceedings of SIGMETRICS 2008",
  year = "2008",
         url_paper =  {https://www.boazbarak.org/Papers/sigfd.pdf},
  }

Universal Arguments and their Applications. Barak, B.; and Goldreich, O. SIAM Journal on Computing, 38(5): 1661-1694. 2008. Preliminary version in CCC' 02

Universal Arguments and their Applications [link]

powerpoint

Universal Arguments and their Applications [ps]

ps link bibtex 4 downloads

@article{BarakGo02,
author = {Boaz Barak and Oded Goldreich},
collaboration = {},
title = {Universal Arguments and their Applications},
publisher = {SIAM},
year = {2008},
journal = {SIAM Journal on Computing},
volume = {38},
number = {5},
pages = {1661-1694},
 url_powerpoint = {https://www.boazbarak.org/Papers/uargs.pps},
note  = {Preliminary version in CCC' 02},
    url_ps = {https://www.boazbarak.org/Papers/uargs.ps},
prelimYear = {2002},
}

2007 (2)

Lower bounds on signatures from symmetric primitives. Barak, B.; and Mahmoody-Ghidary, M. In Proceedings of FOCS '07, 2007.

Lower bounds on signatures from symmetric primitives [pdf]

paper link bibtex

@InProceedings{BarakGh07,
    title  = "Lower bounds on signatures from symmetric primitives",
    author = "Boaz Barak and Mohammad Mahmoody-Ghidary",
    booktitle = {Proceedings of FOCS '07},
    year = "2007",
         url_paper =  {https://www.boazbarak.org/Papers/siglb.pdf},
    }

Privacy, accuracy, and consistency too: a holistic solution to contingency table release. Barak, B.; Chaudhuri, K.; Dwork, C.; Kale, S.; McSherry, F.; and Talwar, K. In Libkin, L., editor(s), Proceedings of ACM PODS, pages 273–282, 2007. ACM

Privacy, accuracy, and consistency too: a holistic solution to contingency table release [pdf]

paper link bibtex

@InProceedings{BarakChDwKaMcTa07,
  title =	"Privacy, accuracy, and consistency too: a holistic
		 solution to contingency table release",
  author =	"Boaz Barak and Kamalika Chaudhuri and Cynthia Dwork
		 and Satyen Kale and Frank McSherry and Kunal Talwar",
  booktitle =	"Proceedings of ACM PODS",
  publisher =	"ACM",
  year = 	"2007",
  editor =	"Leonid Libkin",
  ISBN = 	"978-1-59593-685-1",
  pages =	"273--282",
   url_paper =  {https://www.boazbarak.org/Papers/privacy.pdf},
}

2006 (3)

Concurrent Non-Malleable Zero Knowledge. Barak, B.; Prabhakaran, M.; and Sahai, A. In Proceedings of FOCS '06, 2006.

Concurrent Non-Malleable Zero Knowledge [pdf]

paper link bibtex 3 downloads

@InProceedings{BarakPeSa06,
author = "Boaz Barak and Manoj Prabhakaran and Amit Sahai",
title = "Concurrent Non-Malleable Zero Knowledge",
booktitle = {Proceedings of FOCS '06},
year = "2006",
   url_paper =  {https://www.boazbarak.org/Papers/cnmzk.pdf},
}

Extracting Randomness Using Few Independent Sources. Barak, B.; Impagliazzo, R.; and Wigderson, A. SIAM Journal on Computing, 36(4): 1095-1118. 2006. Preliminary version in FOCS' 04

Extracting Randomness Using Few Independent Sources [pdf]

paper

Extracting Randomness Using Few Independent Sources [link]

powerpoint link bibtex 4 downloads

@article{BarakImWi04,
author = {Boaz Barak and Russell Impagliazzo and Avi Wigderson},
collaboration = {},
title = {Extracting Randomness Using Few Independent Sources},
publisher = {SIAM},
year = {2006},
journal = {SIAM Journal on Computing},
volume = {36},
number = {4},
pages = {1095-1118},
 ps = {https://www.boazbarak.org/Papers/msamples.ps},
  url_paper = {https://www.boazbarak.org/Papers/msamples.pdf},
  url_powerpoint = {https://www.boazbarak.org/Papers/msamples.pps},
 prelimYear = "2004",
 note = "Preliminary version in FOCS' 04",
}

Lower bounds for non-black-box zero knowledge. Barak, B.; Lindell, Y.; and Vadhan, S. J. Comput. Syst. Sci, 72(2): 321–391. 2006. Preliminary version in FOCS' 03

Lower bounds for non-black-box zero knowledge [pdf]

paper

Lower bounds for non-black-box zero knowledge [link]

powerpoint link bibtex 3 downloads

@Article{BarakLiVa06,
  title =   "Lower bounds for non-black-box zero knowledge",
  author =  "Boaz Barak and Yehuda Lindell and Salil Vadhan",
  journal = "J. Comput. Syst. Sci",
  year =    "2006",
  number =  "2",
  volume =  "72",
  bibdate = "2006-07-25",
  bibsource =   "DBLP,
         http://dblp.uni-trier.de/db/journals/jcss/jcss72.html#BarakLV06",
  pages =   "321--391",
  note = {Preliminary version in FOCS' 03},
  ps = {https://www.boazbarak.org/Papers/zklower.ps},
   url_paper = {https://www.boazbarak.org/Papers/zklower.pdf},
   url_powerpoint = {https://www.boazbarak.org/Papers/zklower.pps},
  prelimYear = {2003},
}

2005 (4)

An architecture for robust pseudo-random generation and Applications to /dev/random. Barak, B.; and Halevi, S. In ACM, editor(s), Proc. Computing and Communication Security (CCS), 2005.

An architecture for robust pseudo-random generation and Applications to /dev/random [ps]

ps

An architecture for robust pseudo-random generation and Applications to /dev/random [pdf]

paper link bibtex 2 downloads

@InProceedings{BarakHa05,
 author = "Boaz Barak and Shai Halevi",
 title = "An architecture for robust pseudo-random generation
           and Applications to /dev/random",
           year= "2005",
           booktitle = "Proc. Computing and Communication Security (CCS)",
           editor = "ACM",
           url_ps =  {https://www.boazbarak.org/Papers/devrand.ps},
            url_paper =  {https://www.boazbarak.org/Papers/devrand.pdf},
           }

How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation. Barak, B.; and Sahai, A. In Proceedings of FOCS '05, 2005.

How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation [ps]

ps

How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation [pdf]

paper

How to Play Almost Any Mental Game Over the Net - Concurrent Composition Using Super-Polynomial Simulation [link]

powerpoint link bibtex 3 downloads

@InProceedings{BarakSa05,
  author =       "Boaz Barak and Amit Sahai",
  title =        "How to Play Almost Any Mental Game Over the Net -
  Concurrent Composition Using Super-Polynomial Simulation",
  year =         "2005",
  booktitle = {Proceedings of FOCS '05},
     url_ps =  {https://www.boazbarak.org/Papers/conc-comp.ps},
     url_paper =  {https://www.boazbarak.org/Papers/conc-comp.pdf},
     url_powerpoint =  {https://www.boazbarak.org/Papers/conc-comp.pps},
}

Secure Computation Without Authentication. Barak, B.; Canetti, R.; Lindell, Y.; Pass, R.; and Rabin, T. In Proceedings of CRYPTO '05, 2005.

Secure Computation Without Authentication [link]

paper link bibtex 2 downloads

@InProceedings{BarakCaLiPaRa05,
  author =       {Boaz Barak and Ran Canetti and Yehuda Lindell and Rafael Pass and Tal Rabin},
  title =        {Secure Computation Without Authentication},
  booktitle = {Proceedings of CRYPTO '05},
  year = {2005},
   url_paper =  {http://dx.doi.org/10.1007/11535218_22},
}

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors. Barak, B.; Kindler, G.; Shaltiel, R.; Sudakov, B.; and Wigderson, A. In Proceedings of STOC '05, 2005.

Simulating Independence: New Constructions of Condensers, Ramsey Graphs, Dispersers, and Extractors [pdf]

paper link bibtex 4 downloads

@InProceedings{BarakKiShSuWi05,
author = {Boaz Barak and Guy Kindler and Ronen Shaltiel and Benjamin Sudakov and Avi Wigderson},
title = {Simulating Independence: New Constructions of Condensers, Ramsey
   Graphs, Dispersers, and Extractors},
   year = {2005},
 booktitle = {Proceedings of STOC '05},
   ps =  {https://www.boazbarak.org/Papers/BKSSW.ps},
       url_paper =  {https://www.boazbarak.org/Papers/BKSSW.pdf},
}

2004 (4)

Non-Black-Box Techniques in Cryptography. Barak, B. Ph.D. Thesis, Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel, 2004.
link bibtex

@PHDTHESIS{Barak04thesis,
  author =       {Boaz Barak},
  title =        {Non-Black-Box Techniques in Cryptography},
  school =       {Department of Computer Science and Applied Mathematics, Weizmann Institute of Science, Rehovot, Israel},
  year =         {2004},
}

Universally Composable Protocols with Relaxed Set-Up Assumptions. Barak, B.; Canetti, R.; Nielsen, J. B.; and Pass, R. In Proceedings of FOCS '04, pages 186–195, 2004.

Universally Composable Protocols with Relaxed Set-Up Assumptions [pdf]

paper link bibtex 2 downloads

@InProceedings{BarakCaNiPa04,
  author =       "Boaz Barak and Ran Canetti and Jesper Buus Nielsen and Rafael Pass",
  title =        "Universally Composable Protocols with Relaxed Set-Up
                 Assumptions",
  year =         "2004",
  pages = "186--195",
  booktitle = {Proceedings of FOCS '04},
  ps =  {https://www.boazbarak.org/Papers/ucpki.ps},
     url_paper =  {https://www.boazbarak.org/Papers/ucpki.pdf},
}

On the Possibility of One-Message Weak Zero-Knowledge. Barak, B.; and Pass, R. In First Theory of Cryptography Conference (TCC), 2004.

On the Possibility of One-Message Weak Zero-Knowledge [pdf]

paper link bibtex 4 downloads

@inproceedings{BarakPa04,
    author = {Boaz Barak and Rafael Pass},
    title = {On the Possibility of One-Message Weak Zero-Knowledge},
    booktitle = {First Theory of Cryptography Conference (TCC)},
    year = {2004},
    ps = {https://www.boazbarak.org/Papers/uniformNIZK.ps},
     url_paper = {https://www.boazbarak.org/Papers/uniformNIZK.pdf},
}

Strict Polynomial-Time in Simulation and Extraction. Barak, B.; and Lindell, Y. SIAM Journal on Computing, 33(4): 783–818. August 2004. Extended abstract appeared in STOC 2002

Strict Polynomial-Time in Simulation and Extraction [pdf]

paper link bibtex 7 downloads

@Article{BarakLi02,
  author =       "Boaz Barak and Yehuda Lindell",
  title =        "Strict Polynomial-Time in Simulation and Extraction",
  journal =      "SIAM Journal on Computing",
  volume =       "33",
  number =       "4",
  pages =        "783--818",
  month =        aug,
  year =         "2004",
  CODEN =        "SMJCAT",
  ISSN =         "0097-5397 (print), 1095-7111 (electronic)",
  bibdate =      "Sat Apr 16 10:19:24 MDT 2005",
   acknowledgement = ack-nhfb,
  prelimYear = {2002},
  note = {Extended abstract appeared in STOC 2002},
    ps = {https://www.boazbarak.org/Papers/zkpok.ps},
     url_paper = {https://www.boazbarak.org/Papers/zkpok.pdf},
}

2003 (3)

True Random Number Generators Secure in a Changing Environment. Barak, B.; Shaltiel, R.; and Tromer, E. In Workshop on Cryptographic Hardware and Embedded Systems (CHES), of LNCS, pages 166–180, 2003.

True Random Number Generators Secure in a Changing Environment [pdf]

paper

True Random Number Generators Secure in a Changing Environment [link]

powerpoint link bibtex 3 downloads

@INPROCEEDINGS{BarakShTr03,
  AUTHOR =       {Boaz Barak and Ronen Shaltiel and Eran Tromer},
  TITLE =        {True Random Number Generators Secure in a Changing Environment},
  BOOKTITLE =    {Workshop on Cryptographic Hardware and Embedded Systems (CHES)},
  YEAR =         {2003},
  number =       {2779},
  series =       {LNCS},
  pages =        {166--180},
  ps = {https://www.boazbarak.org/Papers/trng.ps},
   url_paper = {https://www.boazbarak.org/Papers/trng.pdf},
   url_powerpoint = {https://www.boazbarak.org/Papers/trng.pps},
}

Computational analogues of entropy. Barak, B.; Shaltiel, R.; and Wigderson, A. In Proc. of $7$th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2003. See erratum note in abstract.

Computational analogues of entropy [pdf]

paper

Computational analogues of entropy [link]

powerpoint link bibtex 5 downloads

@inproceedings{BarakShWi03,
 author = {Boaz Barak and Ronen Shaltiel and Avi Wigderson},
 title = {Computational analogues of entropy},
 booktitle ={Proc. of $7$th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)},
 year ={2003},
 note = {See erratum note in abstract.},
  url_paper = {https://www.boazbarak.org/Papers/compent.pdf},
  url_powerpoint = {https://www.boazbarak.org/Papers/compent.pps},
}

Derandomization in Cryptography. Barak, B.; Ong, S. J.; and Vadhan, S. In Proceedings of CRYPTO '03, 2003.

paper

powerpoint link bibtex 6 downloads

@INPROCEEDINGS{BarakOnVa03,
  author =       "Barak, Boaz and Ong, Shien Jin and Vadhan, Salil",
  title =        "Derandomization in Cryptography",
  year =         "2003",
  booktitle = {Proceedings of CRYPTO '03},
  ps = {https://www.boazbarak.org/Papers/derand-crypto.ps},
   url_paper = {https://www.boazbarak.org/Papers/derand-crypto.pdf},
   url_powerpoint = {https://www.boazbarak.org/Papers/derand-crypto.pps},
}

2002 (2)

A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms. Barak, B. In Proc. of $6$th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM), 2002.

A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms [ps]

ps link bibtex 3 downloads

@INPROCEEDINGS{Barak02bpp,
  AUTHOR =       {Boaz Barak},
  TITLE =        {A Probabilistic-Time Hierarchy Theorem for ``Slightly Non-Uniform'' Algorithms},
  BOOKTITLE =    {Proc. of $6$th Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM)},
  YEAR =         {2002},
  url_ps = {https://www.boazbarak.org/Papers/bptime.ps},
}

Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model. Barak, B. In Proceedings of FOCS '02, 2002. See also my thesis.

Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model [pdf]

paper

Constant-Round Coin-Tossing With a Man in the Middle or Realizing the Shared Random String Model [link]

powerpoint link bibtex 5 downloads

@inproceedings{Barak02,
  AUTHOR =       "Boaz Barak",
  TITLE =        "Constant-Round Coin-Tossing With a Man in the Middle or  Realizing the Shared Random String Model",
  YEAR =         "2002",
  booktitle = {Proceedings of FOCS '02},
  note = {See also my thesis.},
   url_paper = {https://www.boazbarak.org/Papers/nmc.pdf},
   url_powerpoint = {https://www.boazbarak.org/Papers/nmc.pps},
}

2001 (3)

Delegateable Signatures. Barak, B. Technical Report 2001.

ps link bibtex 1 download

@TECHREPORT{Barak01delg,
  AUTHOR =       {Boaz Barak},
  TITLE =        {Delegateable Signatures},
  YEAR =         {2001},
  url_ps =  {https://www.boazbarak.org/Papers/delgsigs.ps},
}

Resettably-Sound Zero-Knowledge and its Applications. Barak, B.; Goldreich, O.; Goldwasser, S.; and Lindell, Y. In Proceedings of FOCS '01, pages 116–125, 2001.

Resettably-Sound Zero-Knowledge and its Applications [ps]

ps link bibtex

@inproceedings{BarakGoGoLi01,
  author =       "Boaz Barak and Oded Goldreich and Shafi Goldwasser and
                 Yehuda Lindell",
  title =        "Resettably-Sound Zero-Knowledge and its Applications",
    pages =        "116--125",
  booktitle = {Proceedings of FOCS '01},
  year = {2001},
  url_ps = {https://www.boazbarak.org/Papers/rszk.ps},
}

How to go beyond the black-box simulation barrier. Barak, B. In Proceedings of FOCS '01, pages 106–115, 2001. Winner, FOCS 2021 Test of Time Award

How to go beyond the black-box simulation barrier [pdf]

paper link bibtex 21 downloads

@InProceedings{Barak01,
  author =       "Boaz Barak",
  title =        "How to go beyond the black-box simulation barrier",
  year =         "2001",
  pages =        "106--115",
  booktitle = {Proceedings of FOCS '01},
  year = {2001},
    note = {Winner, FOCS 2021 Test of Time Award},
   url_paper = {https://www.boazbarak.org/Papers/nonbb.pdf},
   selected = {yes},
}

2000 (1)

Clock Synchronization with Faults and Recoveries. Barak, B.; Halevi, S.; Herzberg, A.; and Naor, D. In Proc. of 19$th$ ACM Principles of Distributed Computing (PODC), 2000. ACM

ps link bibtex 1 download

@inproceedings{BarakHaHeNa00,
author="Boaz Barak and Shai Halevi and Amir Herzberg and Dalit Naor",
title = "Clock Synchronization with Faults and Recoveries",
booktitle={Proc. of 19$th$ ACM Principles of Distributed Computing (PODC)},
publisher = {ACM},
year = {2000},
url_ps = {https://www.boazbarak.org/Papers/clockSyn-proc.ps},
}

1999 (1)

The Proactive Security Toolkit and Applications. Barak, B.; Herzberg, A.; Naor, D.; and Shai, E. In Proc. of 6$^{th}$ ACM Conference on Computer and Communications Security (CCS), 1999. ACM

The Proactive Security Toolkit and Applications [ps]

ps link bibtex

@inproceedings{BarakHeNaSh99,
author="Boaz Barak and Amir Herzberg and  Dalit Naor and Eldad Shai",
title = "The Proactive Security Toolkit and Applications",
booktitle="Proc. of 6$^{th}$ ACM Conference on Computer and Communications
Security (CCS)",
publisher ={ACM},
year = {1999},
url_ps = {https://www.boazbarak.org/Papers/proactivePaper-proc.ps},
}


% END OF BIBITEMS
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CROSSREFS