2. ICS 2011: Tsinghua University, Beijing, China

• Ueli Maurer, Renato Renner:
  Abstract Cryptography. 1-21
  
• Brendan Juba, Madhu Sudan:
  Efficient Semantic Communication via Compatible Beliefs. 22-31
  
• Shlomi Dolev, Juan A. Garay, Niv Gilboa, Vladimir Kolesnikov:
  Secret Sharing Krohn-Rhodes: Private and Perennial Distributed Computation. 32-44
  
• Benny Applebaum, Danny Harnik, Yuval Ishai:
  Semantic Security under Related-Key Attacks and Applications. 45-60
  
• Rafael Pass, Abhi Shelat:
  Renegotiation-Safe Protocols. 61-78
  
• Brendan Juba, Adam Tauman Kalai, Sanjeev Khanna, Madhu Sudan:
  Compression without a common prior: an information-theoretic justification for ambiguity in language. 79-86
  
• Maurice J. Jansen:
  Extracting Roots of Arithmetic Circuits by Adapting Numerical Methods. 87-100
  
• Yi Wu:
  Pricing Loss Leaders can be Hard. 101-111
  
• Thanh Nguyen:
  Revenue Maximization via Nash Implementation. 112-124
  
• Robert D. Kleinberg, Katrina Ligett, Georgios Piliouras, Éva Tardos:
  Beyond the Nash Equilibrium Barrier. 125-140
  
• Xi Chen, Shang-Hua Teng:
  A Complexity View of Markets with Social Influence. 141-154
  
• Noam Nisan, Michael Schapira, Gregory Valiant, Aviv Zohar:
  Best-Response Mechanisms. 155-165
  
• Moshe Babaioff, Liad Blumrosen, Shaddin Dughmi, Yaron Singer:
  Posting Prices with Unknown Distributions. 166-178
  
• Reut Levi, Dana Ron, Ronitt Rubinfeld:
  Testing Properties of Collections of Distributions. 179-194
  
• C. Seshadhri, Jan Vondrák:
  Is Submodularity Testable? 195-210
  
• Victor Chen, Madhu Sudan, Ning Xie:
  Property Testing via Set-Theoretic Operations. 211-222
  
• Ronitt Rubinfeld, Gil Tamir, Shai Vardi, Ning Xie:
  Fast Local Computation Algorithms. 223-238
  
• Arnab Bhattacharyya, Eldar Fischer, Ronitt Rubinfeld, Paul Valiant:
  Testing monotonicity of distributions over general partial orders. 239-252
  
• Thomas Dueholm Hansen, Peter Bro Miltersen, Uri Zwick:
  Strategy iteration is strongly polynomial for 2-player turn-based stochastic games with a constant discount factor. 253-263
  
• Sourav Chakraborty, Eldar Fischer, Arie Matsliah:
  Query Complexity Lower Bounds for Reconstruction of Codes. 264-274
  
• Ryan O'Donnell, Yi Wu, Yuan Zhou:
  Optimal lower bounds for locality sensitive hashing (except when q is tiny). 275-283
  
• Sourav Chakraborty, David García-Soriano, Arie Matsliah:
  Cycle Detection, Order Finding and Discrete Log with Jumps. 284-297
  
• Henry Cohn, Nadia Heninger:
  Ideal forms of Coppersmith's theorem and Guruswami-Sudan list decoding. 298-308
  
• Pascal Koiran:
  Shallow circuits with high-powered inputs. 309-320
  
• Venkatesan Guruswami, Yury Makarychev, Prasad Raghavendra, David Steurer, Yuan Zhou:
  Finding Almost-Perfect Graph Bisections. 321-337
  
• Scott Aaronson, Andris Ambainis:
  The Need for Structure in Quantum Speedups. 338-352
  
• Mark Braverman, Avinatan Hassidim, Yael Tauman Kalai:
  Leaky Pseudo-Entropy Functions. 353-366
  
• Satyen Kale, C. Seshadhri:
  Combinatorial Approximation Algorithms for MaxCut using Random Walks. 367-388
  
• Christian Borgs, Jennifer T. Chayes, Jian Ding, Brendan Lucier:
  The Hitchhiker's Guide to Affiliation Networks: A Game-Theoretic Approach. 389-400
  
• Eli Ben-Sasson, Jakob Nordström:
  Understanding Space in Proof Complexity: Separations and Trade-offs via Substitutions. 401-416
  
• Aaron D. Jaggard, Michael Schapira, Rebecca N. Wright:
  Distributed Computing with Adaptive Heuristics. 417-443
  
• Konstantin Makarychev, Alantha Newman:
  Complex Semidefinite Programming Revisited and the Assembly of Circular Genomes. 444-459
  
• Zeev Dvir, Dan Gutfreund, Guy N. Rothblum, Salil P. Vadhan:
  On Approximating the Entropy of Polynomial Mappings. 460-475
  
• Noga Alon, Yuval Emek, Michal Feldman, Moshe Tennenholtz:
  Economical Graph Discovery. 476-486
  
• Satyen Kale, Ravi Kumar, Sergei Vassilvitskii:
  Cross-Validation and Mean-Square Stability. 487-495
  
• Arnab Bhattacharyya, Piotr Indyk, David P. Woodruff, Ning Xie:
  The Complexity of Linear Dependence Problems in Vector Spaces. 496-508
  
• Petros Mol, Andrea Vattani, Panagiotis Voulgaris:
  The Effects of Diversity in Aggregation Games. 509-521
  
• Matei David, Phuong Nguyen, Periklis A. Papakonstantinou, Anastasios Sidiropoulos:
  Computationally Limited Randomness. 522-536
  

Last update Fri May 25 08:22:54 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page