3. ITCS 2012: Cambridge, MA, USA

• Andrew Drucker:
  High-confidence predictions under adversarial uncertainty. 1-10
  
• Varun Kanade, Thomas Steinke:
  Learning hurdles for sleeping experts. 11-18
  
• Zeev Dvir, Anup Rao, Avi Wigderson, Amir Yehudayoff:
  Restriction access. 19-33
  
• Alessandro Chiesa, Silvio Micali, Zeyuan Allen Zhu:
  Mechanism design with approximate valuations. 34-38
  
• Shengyu Zhang:
  Quantum strategic game theory. 39-59
  
• Renato Paes Leme, Vasilis Syrgkanis, Éva Tardos:
  The curse of simultaneity. 60-67
  
• Danny Dolev, Dror G. Feitelson, Joseph Y. Halpern, Raz Kupferman, Nathan Linial:
  No justified complaints: on fair sharing of multiple resources. 68-75
  
• Yuval Ishai, Eyal Kushilevitz, Anat Paskin-Cherniavsky:
  From randomizing polynomials to parallel algorithms. 76-89
  
• Graham Cormode, Michael Mitzenmacher, Justin Thaler:
  Practical verified computation with streaming interactive proofs. 90-112
  
• Alejandro López-Ortiz, Alejandro Salinger:
  Paging for multi-core shared caches. 113-127
  
• Mark Braverman, Alexander Grigo, Cristobal Rojas:
  Noise vs computational intractability in dynamics. 128-141
  
• Paul Valiant:
  Distribution free evolvability of polynomial functions over all convex loss functions. 142-148
  
• Aris Anagnostopoulos, Ravi Kumar, Mohammad Mahdian, Eli Upfal, Fabio Vandin:
  Algorithms on evolving graphs. 149-160
  
• Mark Braverman:
  Towards deterministic tree code constructions. 161-167
  
• Michael Viderman:
  Linear time decoding of regular expander codes. 168-182
  
• Venkatesan Guruswami, Srivatsan Narayanan, Carol Wang:
  List decoding subspace codes from insertions and deletions. 183-189
  
• Gillat Kol, Ran Raz:
  Bounds on locally testable codes with unique tests. 190-202
  
• Kobbi Nissim, Rann Smorodinsky, Moshe Tennenholtz:
  Approximately optimal mechanism design via differential privacy. 203-213
  
• Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel:
  Fairness through awareness. 214-226
  
• Vahideh H. Manshadi, Amin Saberi:
  Dynamics of prisoner's dilemma and the evolution of cooperation on networks. 227-235
  
• Pablo Azar, Jing Chen, Silvio Micali:
  Crowdsourced Bayesian auctions. 236-248
  
• Bohua Zhan, Shelby Kimmel, Avinatan Hassidim:
  Super-polynomial quantum speed-ups for boolean evaluation trees with hidden structure. 249-265
  
• Tsuyoshi Ito, Hirotada Kobayashi, John Watrous:
  Quantum interactive proofs with weak error bounds. 266-275
  
• Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, Peter W. Shor:
  Quantum money from knots. 276-289
  
• Maris Ozols, Martin Roetteler, Jérémie Roland:
  Quantum rejection sampling. 290-308
  
• Zvika Brakerski, Craig Gentry, Vinod Vaikuntanathan:
  (Leveled) fully homomorphic encryption without bootstrapping. 309-325
  
• Nir Bitansky, Ran Canetti, Alessandro Chiesa, Eran Tromer:
  From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. 326-349
  
• Dan Boneh, Gil Segev, Brent Waters:
  Targeted malleability: homomorphic encryption for restricted computations. 350-366
  
• Albert Atserias, Elitza N. Maneva:
  Sherali-Adams relaxations and indistinguishability in counting logics. 367-379
  
• Moritz Hardt, Nikhil Srivastava, Madhur Tulsiani:
  Graph densification. 380-392
  
• Michael Kapralov, Rina Panigrahy:
  Spectral sparsification via random spanners. 393-398
  
• Chandra Chekuri, Sreeram Kannan, Adnan Raja, Pramod Viswanath:
  Multicommodity flows and cuts in polymatroidal networks. 399-408
  
• Gil Cohen, Amir Shpilka, Avishay Tal:
  On the degree of univariate polynomials over the integers. 409-427
  
• David Letscher:
  On persistent homotopy, knotted complexes and the Alexander module. 428-441
  
• Rasmus Pagh:
  Compressed matrix multiplication. 442-451
  
• Jin-yi Cai, Michael Kowalczyk, Tyson Williams:
  Gadgets and anti-gadgets leading to a complexity dichotomy. 452-467
  
• Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
  On beating the hybrid argument. 468-483
  
• Gábor Kun, Ryan O'Donnell, Suguru Tamaki, Yuichi Yoshida, Yuan Zhou:
  Linear programming, width-1 CSPs, and robust satisfaction. 484-495
  
• Maurice J. Jansen, Rahul Santhanam:
  Marginal hitting sets imply super-polynomial lower bounds for permanent. 496-506
  

Last update Sat May 25 03:42:29 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page