Journal of the ACM, Volume 59

Volume 59, Number 1, February 2012

• Christel Baier, Marcus Größer, Nathalie Bertrand:
  Probabilistic ω-automata. 1
  
• James Aspnes, Hagit Attiya, Keren Censor-Hillel:
  Polylogarithmic concurrent data structures from monotone circuits. 2
  
• Armando Castañeda, Sergio Rajsbaum:
  New combinatorial topology bounds for renaming: The upper bound. 3
  
• Victor Vianu:
  Invited article foreword. 4
  
• Martin Otto:
  Highly acyclic groups, hypergraph covers, and the guarded fragment. 5
  

Volume 59, Number 2, April 2012

• Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang:
  On the (im)possibility of obfuscating programs. 6
  
• Vijay V. Vazirani:
  The notion of a rational convex program, and an algorithm for the arrow-debreu Nash bargaining game. 7
  
• Oded Goldreich, Brendan Juba, Madhu Sudan:
  A theory of goal-oriented communication. 8
  
• Victor Vianu:
  Invited article foreword. 9
  
• Graham Cormode, S. Muthukrishnan, Ke Yi, Qin Zhang:
  Continuous sampling from distributed streams. 10
  

Volume 59, Number 3, June 2012

• Jens Groth, Rafail Ostrovsky, Amit Sahai:
  New Techniques for Noninteractive Zero-Knowledge. 11
  
• Adam Kirsch, Michael Mitzenmacher, Andrea Pietracaprina, Geppino Pucci, Eli Upfal, Fabio Vandin:
  An Efficient Rigorous Approach for Identifying Statistically Significant Frequent Itemsets. 12
  
• Hagen Völzer, Daniele Varacca:
  Defining Fairness in Reactive and Concurrent Systems. 13
  
• Mihai Patrascu, Mikkel Thorup:
  The Power of Simple Tabulation Hashing. 14
  
• Victor Vianu:
  Invited Article Foreword. 15
  
• Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, Paul Valiant:
  Size and Treewidth Bounds for Conjunctive Queries. 16
  

Volume 59, Number 4, August 2012

• Yijia Chen, Jörg Flum:
  From Almost Optimal Algorithms to Logics for Complexity Classes via Listings and a Halting Problem. 17
  
• Chen Avin, Yuval Emek, Erez Kantor, Zvi Lotker, David Peleg, Liam Roditty:
  SINR Diagrams: Convexity and Its Applications in Wireless Networks. 18
  
• Nikhil Bansal, Niv Buchbinder, Joseph Naor:
  A Primal-Dual Randomized Algorithm for Weighted Paging. 19
  
• Victor Vianu:
  Invited Article Foreword. 20
  
• Ke Yi:
  Dynamic Indexability and the Optimality of B-Trees. 21
  

Volume 59, Number 5, October 2012

• Ashwinkumar Badanidiyuru, Arpita Patra, Ashish Choudhury, Kannan Srinathan, C. Pandu Rangan:
  On the trade-off between network connectivity, round complexity, and communication complexity of reliable message transmission. 22
  
• Kenneth L. Clarkson, Elad Hazan, David P. Woodruff:
  Sublinear optimization for machine learning. 23
  
• Andris Ambainis, Julia Kempe, Or Sattath:
  A quantum lovász local lemma. 24
  
• Leslie Ann Goldberg, Mark Jerrum:
  Approximating the partition function of the ferromagnetic potts model. 25
  
• Victor Vianu:
  Invited article foreword. 26
  
• Martin Grohe:
  Fixed-point definability and polynomial time on graphs with excluded minors. 27
  

Volume 59, Number 6, December 2012

• Rafail Ostrovsky, Yuval Rabani, Leonard J. Schulman, Chaitanya Swamy:
  The effectiveness of lloyd-type methods for the k-means problem. 28
  
• Prahladh Harsha, Adam Klivans, Raghu Meka:
  An invariance principle for polytopes. 29
  
• Nilesh N. Dalvi, Dan Suciu:
  The dichotomy of probabilistic inference for unions of conjunctive queries. 30
  
• Patrick Cousot, Radhia Cousot, Laurent Mauborgne:
  Theories, solvers and static analysis by abstract interpretation. 31
  
• Grey Ballard, James Demmel, Olga Holtz, Oded Schwartz:
  Graph expansion and communication costs of fast matrix multiplication. 32
  

Last update Tue May 21 19:10:37 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page