Welcome to Innovations in Computer Science 2010

January 5-7, 2010

Beijing, China

http://conference.itcs.tsinghua.edu.cn/ICS2010/

Organized by: Institute for Theoretical Computer Science, Tsinghua University

Conference Venue: Lecture Hall of FIT Building, Tsinghua University

General Chair:  Prof. Andrew Yao, Tsinghua University

Sponsored by

The Ministry of Science and Technology of the People’s Republic of China

The Ministry of Education of the People’s Republic of China

National Natural Science Foundation of China

National Basic Research Program of China

Tsinghua University

Institute for Theoretical Computer Science, Tsinghua Universtiy

Steering Committee

Sanjeev Arora (Princeton University)
Manuel Blum  (Carnegie Mellon University)

Bernard Chazelle (Princeton University)
Oded Goldreich (Weizmann Institute of Science, Israel)
Shafi Goldwasser  (MIT and Weizmann Institute)
Richard Karp (UC Berkeley) 
Silvio Micali (MIT)
Christos Papadimitriou (University of California, Berkeley)
Michael Rabin (Harvard University)
Madhu Sudan (MIT)
Leslie Valiant (Harvard University)
Umesh Vazirani ( University of California, Berkeley)
Avi Wigderson (Institute for Advanced Study, Princeton)
Andrew Yao (Tsinghua University)

ICS 2010 Program Committee

Andrew Yao  (Tsinghua University)
Michael Ben-Or (The Hebrew University, Israel)
Avrim Blum (Carnegie Mellon University)
Cynthia Dwork (Microsoft Research, Silicon Valley)
Shafi Goldwasser (MIT and Weizmann Institute)
Michael Kearns (University of Pennsylvania)
Sanjeev Khanna (University of Pennsylvania)
Ming Li (University of Waterloo)
Christos Papadimitriou (University of California, Berkeley)
Rafael Pass ( Cornell University)
Nir Shavit (Tel Aviv University, Israel)
Vijay Vazirani (Georgia Institute of Technology)

===========================

Introduction

Innovations in Computer Science (ICS) is a new conference in theoretical computer science, broadly construed. ICS seeks to promote research that carries a strong conceptual message (e.g., introducing a new concept or model, opening a new line of inquiry within traditional or cross-disciplinary areas, or introducing novel techniques or novel applications of known techniques). ICS welcomes all submissions whether they are aligned with the current TCS research directions or transcend these boundaries.
ICS is a public conference designed to run in a workshop-like environment. The conference will run for two-and-a-half days. The total number of papers will be around 30, so as to allow for ample time for open and one-on-one discussions and exchanges of ideas.

Proceedings: The conference proceedings containing all the accepted papers will be published by the Tsinghua University Press, Beijing.

Tentative Program

Tuesday, January 5, 2010

Session 1 (08:30-10:00):

Cryptography by Cellular Automata or How Fast Can Complexity Emerge in Nature?

Benny Applebaum, Yuval Ishai and Eyal Kushilevitz

Breaking and Making Quantum Money: Toward a New Quantum Cryptographic Protocol

Andrew Lutomirski, Scott Aaronson, Edward Farhi, David Gosset, Jonathan Kelner, Avinatan Hassidim and Peter Shor

Analytical Tools for Natural Algorithms

Bernard Chazelle

Session 2 (10:40-11:55):

A New Approach to Strongly Polynomial Linear Programming

Mihály Bárász and Santosh Vempala

Computational Complexity and Information Asymmetry in Financial Products (Extended Abstract)

Sanjeev Arora, Boaz Barak, Markus Brunnermeier and Rong Ge

Pan-Private Streaming Algorithms

Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum and Sergey Yekhanin

Session 3 (14:00-15:40):

Robustly Leveraging Collusion in Combinatorial Auctions

Jing Chen, Silvio Micali and Paul Valiant

Robust Perfect Revenue From Perfectly Informed Players

Jing Chen, Avinatan Hassidim and Silvio Micali

Playing Games without Observing Payoffs

Michal Feldman, Adam Kalai and Moshe Tennenholtz

Adversarial Leakage in Games

Noga Alon, Yuval Emek, Michal Feldman and Moshe Tennenholtz

Session 4 (16:10-17:50):

Game Theory with Costly Computation: Formulation and Application to Protocol Security

Joseph Y. Halpern and Rafael Pass

Bounding Rationality by Discounting Time

Lance Fortnow and Rahul Santhanam

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities

Vijay V. Vazirani and Mihalis Yannakakis

Beyond Equilibria: Mechanisms for Repeated Combinatorial Auctions

Brendan Lucier

Wednesday, January 6, 2010
Session 5 (08:30-10:10):

A New Look at Selfish Routing

Christos Papadimitriou and Gregory Valiant

Local Algorithms for Finding Interesting Individuals in Large Networks

Mickey Brautbar and Michael Kearns

Circumventing the Price of Anarchy: Leading Dynamics to Good Behavior

Maria-Florina Balcan and Avrim Blum and Yishay Mansour

Reaching Consensus on Social Networks

Elchanan Mossel and Grant Schoenebeck

Session 6 (10:40-11:55):

Robustness of the Learning with Errors Assumption

Shafi Goldwasser, Yael Kalai, Chris Peikert and Vinod Vaikuntanathan

Distribution-Specific Agnostic Boosting

Vitaly Feldman

Space-Efficient Estimation of Robust Statistics and Distribution Testing

Steve Chien, Katrina Ligett and Andrew McGregor

Session 7 (14:00-15:40):

Cryptographic Complexity Classes and Computational Intractability Assumptions

Hemanta K. Maji, Manoj Prabhakaran and Mike Rosulek

Hard Instances for Satisfiability and Quasi-one-way Functions

Andrej Bogdanov, Kunal Talwar and Andrew Wan

On the Construction of One-Way Functions from Average Case Hardness

Noam Livne

Proof-Carrying Data and Hearsay Arguments from Signature Cards

Alessandro Chiesa and Eran Tromer

Session 8 (16:10-17:25):

Are Stable Instances Easy?

Yonatan Bilu and Nathan Linial

A New Approximation Technique for Resource-Allocation Problems

Barna Saha and Aravind Srinivasan

Global Alignment of Molecular Sequences via Ancestral State Reconstruction

Alexandr Andoni, Constantinos Daskalakis, Avinatan Hassidim and Sebastien Roch

Thursday, January 7, 2010

Session 9 (08:30-10:00):

Effectively Polynomial Simulations

Toniann Pitassi and Rahul Santhanam

Circuit Lower Bounds, Help Functions, and the Remote Point Problem

V. Arvind and Srikanth Srinivasan

Derandomizing Algorithms on Product Distributions and Other Applications of Order-Based Extraction

Ariel Gabizon and Avinatan Hassidim

Session 10 (10:40-11:55):

Symmetric LDPC Codes and Local Testing

Tali Kaufman and Avi Wigderson

Weight Distribution and List-Decoding Size of Reed-Muller Codes

Tali Kaufman, Shachar Lovett and Ely Porat

Non-Malleable Codes

Stefan Dziembowski, Krzysztof Pietrzak and Daniel Wichs
 
Session 11 (14:00-15:15):

Interactive Proofs For Quantum Computations

Dorit Aharonov, Michael Ben-Or and Elad Eban

On the Power of a Unique Quantum Witness

Rahul Jain, Iordanis Kerenidis,Greg Kuperberg, Miklos Santha, Or Sattath and Shengyu Zhang

Bounds on the Quantum Satisfiability Threshold

Sergey Bravyi, Cristopher Moore and Alexander Russell

Session 12 (15:45-16:35):

Memory Consistency Conditions for Self-Assembly Programming

Aaron Sterling

Cache Replacement Policies for Multicore Processors

Avinatan Hassidim