Theory Matters Wiki

Visions for TCS: Program

Click here for a more detailed version of the program (in MS Word format).

• 8:30-8:45 Registration
• 8:45-9:30 Introductory Remarks: Ed Lazowska, Sanjeev Arora, Sampath Kannan, Salil Vadhan
• 9:30-10:30 Breakout Groups (see below)
• 10:30-10:45 Coffee Break
• 10:45-12:00 Breakout Groups
• 12:00-2:00 Plenary Discussion (over lunch)
• 2:00-4:00 Breakout Groups

Breakout Groups
with members and links to relevant nugget ideas

• Computational Complexity
  Sanjeev Arora, Valentine Kabanets (co-chair), Leonid Levin, Luca Trevisan (co-chair), Avi Wigderson
  • The Factor-Discrete Log Connection
  • P != NP as a law of nature
  • Refining the meaning of "tractable"
  • Security with Certainty
  • Truly Universal Heuristics
  • Understanding patterns

• Data-Centric Computing
  Petros Drineas (co-chair), Piotr Indyk, Sampath Kannan, James Lee (co-chair), Luis Rademacher, Madhu Sudan
  • Theory of Stored Information
  • Algorithms for mining the modern scientific datasets
  • The Limits of Sampling
  • Semantics of Data
  • Spectral data analysis for the masses
  • Understanding patterns

• Economics and Game Theory
  Shuchi Chawla (co-chair), Jason Hartline (co-chair), Anna Karlin, Claire Mathieu, Tim Roughgarden
  • Approximation in economics
  • Complexity and rationality
  • Incorporating Incentives into Algorithm Design
  • Rethinking the Internet's economic structure

• Natural Sciences
  Scott Aaronson (co-chair), Richard Beigel, Bhaskar DasGupta?, Richard Karp, Rocco Servedio (co-chair), Diane Souvaine
  • Efficient computation in the physical world (?)
  • The evolution of networks, great and small
  • Natural Algorithms
  • P != NP as a law of nature
  • Self-assembly of nano-structures
  • Toward a Computational Understanding of the Brain
  • Unraveling the web of interactions in cells

• Parallel Computing, Networks, and Architecture
  Anupam Gupta, Rajmohan Rajaraman, Udi Wieder (co-chair), David Wise, Lisa Zhang (co-chair)
  • A cloud connecting all the computers on planet earth
  • Energy Efficient Computing and Communication
  • Locality, Locality, Locality: A Communication-centric Perspective on Algorithms
  • Programming/algorithm models for the processor-of-the-future

• Security, Privacy, and Reliability
  Cynthia Dwork, Dick Lipton, Kristin Rozier (co-chair), Amit Sahai (co-chair), Salil Vadhan
  • The Factor-Discrete Log Connection
  • Safety-Critical System Verification
  • Secure Program Obfuscation or Functional Secrets
  • Security with Certainty
  • What can be Computed Insensitively?