• 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

• 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

• Approximation in economics
• Complexity and rationality
• Incorporating Incentives into Algorithm Design
• Rethinking the Internet's economic structure

• 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

• 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

• The Factor-Discrete Log Connection
• Safety-Critical System Verification
• Secure Program Obfuscation or Functional Secrets
• Security with Certainty
• What can be Computed Insensitively?

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

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

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

Visions for TCS: Program

Click Attach:Program.doc? for a more detailed version of the program (in MS Word format).

• 8:45-9:30 Introductory Remarks: Ed Lazowska, Sanjeev Arora, Sampath Kannan, Salil Vadhan

Petros Drineas (co-chair), Piotr Indyk, Sampath Kannan, James Lee (co-chair), Luis Rademacher, Madhu Sudan

• 8:30-8:45 Registration
• 8:45-9:30 Introductory Remarks
• 9:30-10:30 Breakout Groups (see below)

Sanjeev Arora, Valentine Kabanets (co-chair), Leonid Levin, Luca Trevisan (co-chair), Avi Wigderson

Petros Drineas (co-chair), Piotr Indyk, Sampath Kannan, James Lee (co-chair), Madhu Sudan

Shuchi Chawla (co-chair), Jason Hartline (co-chair), Anna Karlin, Claire Mathieu, Tim Roughgarden

Scott Aaronson (co-chair), Richard Beigel, Bhaskar DasGupta?, Richard Karp, Rocco Servedio (co-chair), Diane Souvaine

Anupam Gupta, Rajmohan Rajaraman, Udi Wieder (co-chair), David Wise, Lisa Zhang (co-chair)

Cynthia Dwork, Dick Lipton, Kristin Rozier (co-chair), Amit Sahai (co-chair), Salil Vadhan

Sanjeev Arora, Valentine Kabanets, Leonid Levin, Luca Trevisan, Avi Wigderson

Petros Drineas, Piotr Indyk, Sampath Kannan, James Lee, Madhu Sudan

Petros Drineas, Sampath Kannan, James Lee, Madhu Sudan, Santosh Vempala

Sanjeev Arora, Piotr Indyk, Valentine Kabanets, Leonid Levin, Luca Trevisan, Avi Wigderson

• Understanding patterns

with members and links to relevant nugget ideas

• Computational Complexity
  Sanjeev Arora, Piotr Indyk, Valentine Kabanets, Leonid Levin, Luca Trevisan?, Avi Wigderson
  • The Factor-Discrete Log Connection
  • P != NP as a law of nature
  • Refining the meaning of "tractable"

• Data-Centric Computing
  Petros Drineas, Sampath Kannan, James Lee, Madhu Sudan, Santosh Vempala?
  • Theory of Stored Information
  • Algorithms for mining the modern scientific datasets
  • The Limits of Sampling
  • Semantics of Data
  • Spectral data analysis for the masses

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

• Efficient computation in the physical world (?)
• The evolution of networks, great and small

• P != NP as a law of nature
• Self-assembly of nano-structures
• Toward a Computational Understanding of the Brain

• A cloud connecting all the computers on planet earth
• Energy Efficient Computing and Communication
• Locality, Locality, Locality: A Communication-centric Perspective on Algorithms

• Security, Privacy, and Reliability
  Cynthia Dwork, Dick Lipton, Kristin Rozier, Amit Sahai, 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?

Breakout Groups\\

with members and links to relevant nuggets

• P != NP as a law of nature
• Truly Universal Heuristics
• Refining the meaning of "tractable"
• Understanding patterns
• Security with Certainty
• The Factor-Discrete Log Connection

• Natural Algorithms
• Unraveling the web of interactions in cells
• The evolution of networks, great and small
• Toward a Computational Understanding of the Brain
• Efficient computation in the physical world (?)
• Self-assembly of nano-structures
• P != NP as a law of nature

• Programming/algorithm models for the processor-of-the-future
• Locality, Locality, Locality: A Communication-centric Perspective on Algorithms
• Energy Efficient Computing and Communication
• A cloud connecting all the computers on planet earth

• Incorporating Incentives into Algorithm Design
• Rethinking the Internet's economic structure
• Approximation in economics
• Complexity and rationality

• Theory of Stored Information
• Semantics of Data
• Algorithms for mining the modern scientific datasets
• The Limits of Sampling
• Spectral data analysis for the masses

• Secure Program Obfuscation or Functional Secrets
• The Factor-Discrete Log Connection
• Safety-Critical System Verification
• What can be Computed Insensitively?

Cynthia Dwork, Dick Lipton, Kristin Rozier, Amit Sahai, Salil Vadhan

• Security with Certainty

Sanjeev Arora, Piotr Indyk, Valentine Kabanets, Leonid Levin, Luca Trevisan?, Avi Wigderson

Petros Drineas, Sampath Kannan, James Lee, Madhu Sudan, Santosh Vempala?

• Security/privacy/reliability
  Cynthia Dwork, Sampath Kannan, Dick Lipton, Kristin Rozier, Amit Sahai, Salil Vadhan

• Complexity
  Sanjeev Arora, Piotr Indyk, Valentine Kabanets, Leonid Levin, Luca Trevisan, Avi Wigderson

• Natural Sciences
  Scott Aaronson, Richard Beigel, Bhaskar DasGupta?, Richard Karp, Rocco Servedio, Diane Souvaine

• Parallel Computing, Networks, and Architecture
  Anupam Gupta, Rajmohan Rajaraman, Udi Wieder, David Wise, Lisa Zhang

• Economics & Game Theory
  Shuchi Chawla, Jason Hartline, Anna Karlin, Claire Mathieu, Tim Roughgarden

• Data-Centric Computing
  Petros Drineas, James Lee, William Steiger?, Madhu Sudan, Santosh Vempala

Visions for TCS: Tentative Program

• 8:00-8:15 Registration
• 8:15-9:00 Introductory Remarks
• 9:00-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

• Security/privacy/reliability

Members: Cynthia Dwork, Sampath Kannan, Dick Lipton, Kristin Rozier, Amit Sahai, Salil Vadhan

• Security with Certainty
• Secure Program Obfuscation or Functional Secrets
• The Factor-Discrete Log Connection
• Safety-Critical System Verification
• What can be Computed Insensitively?

• Complexity

Members: Sanjeev Arora, Piotr Indyk, Valentine Kabanets, Leonid Levin, Luca Trevisan, Avi Wigderson

• P != NP as a law of nature
• Truly Universal Heuristics
• Refining the meaning of "tractable"
• Understanding patterns
• Security with Certainty
• The Factor-Discrete Log Connection

• Natural Sciences

Members: Scott Aaronson, Richard Beigel, Bhaskar DasGupta?, Richard Karp, Rocco Servedio, Diane Souvaine

• Natural Algorithms
• Unraveling the web of interactions in cells
• The evolution of networks, great and small
• Toward a Computational Understanding of the Brain
• Efficient computation in the physical world (?)
• Self-assembly of nano-structures
• P != NP as a law of nature

• Parallel Computing, Networks, and Architecture

Members: Anupam Gupta, Rajmohan Rajaraman, Udi Wieder, David Wise, Lisa Zhang

• Programming/algorithm models for the processor-of-the-future
• Locality, Locality, Locality: A Communication-centric Perspective on Algorithms
• Energy Efficient Computing and Communication
• A cloud connecting all the computers on planet earth

• Economics & Game Theory

Members: Shuchi Chawla, Jason Hartline, Anna Karlin, Claire Mathieu, Tim Roughgarden

• Incorporating Incentives into Algorithm Design
• Rethinking the Internet's economic structure
• Approximation in economics
• Complexity and rationality

• Data-Centric Computing

Members: Petros Drineas, James Lee, William Steiger?, Madhu Sudan, Santosh Vempala

• Theory of Stored Information
• Semantics of Data
• Algorithms for mining the modern scientific datasets
• The Limits of Sampling
• Spectral data analysis for the masses