Skip to main content

Utility navigation

  • Calendar
  • Contact
  • Login
  • MAKE A GIFT
Berkeley University of California
Home Home

Main navigation

  • Home
  • Programs & Events
    • Research Programs
    • Workshops & Symposia
    • Public Lectures
    • Research Pods
    • Internal Program Activities
    • Algorithms, Society, and the Law
  • People
    • Scientific Leadership
    • Staff
    • Current Long-Term Visitors
    • Research Fellows
    • Postdoctoral Researchers
    • Scientific Advisory Board
    • Governance Board
    • Industry Advisory Council
    • Affiliated Faculty
    • Science Communicators in Residence
    • Law and Society Fellows
  • Participate
    • Apply to Participate
    • Plan Your Visit
    • Location & Directions
    • Postdoctoral Research Fellowships
    • Law and Society Fellowships
    • Science Communicator in Residence Program
    • Circles
    • Breakthroughs Workshops and Goldwasser Exploratory Workshops
  • Support
    • Annual Fund
    • Funders
    • Industrial Partnerships
  • News & Videos
    • News
    • Videos
  • About
Image
Computational Complexity of Statistical Inference_hi-res logo

Average-Case Complexity: From Cryptography to Statistical Learning

Program
Computational Complexity of Statistical Inference
Location

Calvin Lab Auditorium

Date
Monday, Nov. 8 – Wednesday, Nov. 10, 2021
Back to calendar

Breadcrumb

  1. Home
  2. Workshop & Symposia
  3. Schedule

Secondary tabs

  • The Workshop
  • Schedule
  • Videos

9:45 – 10 a.m.
Welcome and Introduction
10 – 10:45 a.m.
On Breaking Encryption With A Statistical Zero-Knowledge Oracle
Andrej Bogdanov (The Chinese University of Hong Kong)
10:45 – 11:15 a.m.
Break
11:15 a.m. – 12:15 p.m.
Average-Case Hardness Of CSPs
Benny Applebaum (Tel-Aviv University)
12:15 – 2 p.m.
Lunch
2 – 3 p.m.
Indistinguishability Obfuscation and Learning Problems
Aayush Jain (NTT Research)
3 – 3:30 p.m.
Break
3:30 – 4:15 p.m.
Low-Complexity Cryptography and Simple Hard-to-Learn Functions
Yuval Ishai (Technion - Israel Institute of Technology)
4:15 – 5:15 p.m.
Reception
10 – 10:30 a.m.
On The Hardness Of Average-Case k-SUM
Noah Stephens-Davidowitz (Cornell University)
10:30 – 11 a.m.
Break
11 a.m. – 12 p.m.
A Few Simple Average-Case Reduction Techniques And Their Surprising Effectiveness
Guy Bresler (MIT)
12 – 2 p.m.
Lunch
2 – 3 p.m.
Open Problems Session
3 – 3:30 p.m.
Break
3:30 – 4:30 p.m.
Analyzing Average-Case Complexity by Meta-Complexity
Shuichi Hirahara (National Institute of Informatics, Tokyo)
10 – 11 a.m.
Sum-Of-Squares Lower Bound for Statistical Problems
Samuel Hopkins (UC Berkeley)
11 – 11:30 a.m.
Break
11:30 a.m. – 12:30 p.m.
Computational trade-offs in graph models
Quentin Berthet (University of Cambridge)
12:30 – 2 p.m.
Lunch
2 – 3 p.m.
Worst-Case Robustness in Machine Learning
Aditi Raghunathan (Stanford)
3 – 3:30 p.m.
Break
3:30 – 4:30 p.m.
On the Cryptographic Hardness of Learning Single Periodic Neurons
Ilias Zadik (Massachusetts Institute of Technology)
Share this page
Copy URL of this page
Home
The Simons Institute for the Theory of Computing is the world's leading venue for collaborative research in theoretical computer science.

Footer

  • Programs & Events
  • About
  • Participate
  • Workshops & Symposia
  • Contact Us
  • Calendar
  • Accessibility

Footer social media

  • Twitter
  • Facebook
  • Youtube
© 2013–2025 Simons Institute for the Theory of Computing. All Rights Reserved.
link to homepage

Main navigation

  • Home
  • Programs & Events
    • Research Programs
    • Workshops & Symposia
    • Public Lectures
    • Research Pods
    • Internal Program Activities
    • Algorithms, Society, and the Law
  • People
    • Scientific Leadership
    • Staff
    • Current Long-Term Visitors
    • Research Fellows
    • Postdoctoral Researchers
    • Scientific Advisory Board
    • Governance Board
    • Industry Advisory Council
    • Affiliated Faculty
    • Science Communicators in Residence
    • Law and Society Fellows
  • Participate
    • Apply to Participate
    • Plan Your Visit
    • Location & Directions
    • Postdoctoral Research Fellowships
    • Law and Society Fellowships
    • Science Communicator in Residence Program
    • Circles
    • Breakthroughs Workshops and Goldwasser Exploratory Workshops
  • Support
    • Annual Fund
    • Funders
    • Industrial Partnerships
  • News & Videos
    • News
    • Videos
  • About

Utility navigation

  • Calendar
  • Contact
  • Login
  • MAKE A GIFT
link to homepage