ICS 2011
Home
About ICS
Program
Contact
iChair
Navigation
Home
Committee
Call for papers
Attendees
Program
Photos
Important Dates
Submission
Accepted Papers
Camera-Ready
Student Grant
Registration
Visa Information
About ICS
Location/Accommodation
Contact
Related Conferences
TTC2011
Sponsors
About Beijing
Current Time
PDT Time
Notification Time
PDT Time
1 Nov 09 - 23:59
paper deadline
PDT Time
Time left
0) { print(Tools::stringTimeLeft($timeLeft)); } else { print("
Time is up!
"); } ?>
Welcome to ICS2011
List of Accepted Papers
In order of submission. (38 papers)
Abstract Cryptography
Ueli Maurer and Renato Renner
Efficient Semantic Communication via Compatible Beliefs
Brendan Juba and Madhu Sudan
Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation
Shlomi Dolev, Juan Garay, Niv Gilboa, Vladimir Kolesnikov
Semantic Security under Related-Key Attacks and Applications
Benny Applebaum and Danny Harnik and Yuval Ishai
Renegotiation-Safe Protocols
Rafael Pass and abhi shelat
Compression without a common prior: an information-theoretic justification for ambiguity in language
Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, and Madhu Sudan
Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods
Maurice Jansen
Pricing Loss Leaders can be Hard
Yi Wu
Revenue Maximization via Nash Implementation
Thanh Nguyen
Beyond the Nash Equilibrium Barrier
Robert Kleinberg, Katrina Ligett, Georgios Piliouras, and Eva Tardos
A Complexity View of Markets with Social Influence
Xi Chen and Shang-Hua Teng
Best-Response Mechanisms
Noam Nisan, Michael Schapira, Greg Valiant and Aviv Zohar
Posting Prices with Unknown Distributions
Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, Yaron Singer
Testing Properties of Collections of Distributions
Reut Levi and Dana Ron and Ronitt Rubinfeld
Is Submodularity Testable?
C. Seshadhri and Jan Vondrak
Property Testing via Set-Theoretic Operations
Victor Chen, Madhu Sudan, Ning Xie
Fast Local Computation Algorithms
Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie
Testing monotonicity of distributions over general partial orders
Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant
Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor
Thomas Dueholm Hansen and Peter Bro Miltersen and Uri Zwick
Query Complexity Lower Bounds for Reconstruction of Codes
Sourav Chakraborty, Eldar Fischer, Arie Matsliah
Optimal lower bounds for locality sensitive hashing (except when q is tiny)
Ryan O'Donnell, Yi Wu, Yuan Zhou
Cycle Detection, Order Finding and Discrete Log with Jumps
Sourav Chakraborty and David Garc\'ia-Soriano and Arie Matsliah
Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding
Henry Cohn and Nadia Heninger
Shallow circuits with high-powered inputs
Pascal Koiran
Finding Almost-Perfect Graph Bisections
Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer and Yuan Zhou
The Need for Structure in Quantum Speedups
Scott Aaronson, Andris Ambainis
Leaky Pseudo-Entropy Functions
Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai
Combinatorial Approximation Algorithms for MaxCut using Random Walks
Satyen Kale and C. Seshadhri
The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach
Christian Borgs, Jennifer Chayes, Jian Ding, Brendan Lucier
Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions
Eli Ben-Sasson and Jakob Nordstrom
Distributed Computing with Adaptive Heuristics
Aaron D. Jaggard, Michael Schapira, and Rebecca N. Wright
Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes
Konstantin Makarychev and Alantha Newman
On Approximating the Entropy of Polynomial Mappings
Zeev Dvir, Dan Gutfreund, Guy Rothblum and Salil Vadhan
Economical Graph Discovery
Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz
Cross-Validation and Mean-Square Stability
Satyen Kale, Ravi Kumar, Sergei Vassilvitskii
The Complexity of Linear Dependence Problems in Vector Spaces
Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie
The Effects of Diversity in Aggregation Games
Petros Mol, Andrea Vattani, Panagiotis Voulgaris
Computationally Limited Randomness
Matei David, Phuong Nguyen, Periklis Papakonstantinou, Anastasios Sidiropoulos
Copyright 2010-2011, Institute for Computer Science, Tsinghua University, All Rights Reserved.
