Volume 40, Number 1, 2011

• 
  Per Austrin, Johan Håstad: Randomly Supported Independence and Resistance. 1-27
• 
  Cheng Shao, Jennifer L. Welch, Evelyn Pierce, Hyunyoung Lee: Multiwriter Consistency Conditions for Shared Memory Registers. 28-62
• 
  Eli Gafni, Rachid Guerraoui, Bastian Pochon: The Complexity of Early Deciding Set Agreement. 63-78
• 
  Elad Hazan, Robert Krauthgamer: How Hard Is It to Approximate the Best Nash Equilibrium? 79-91
• 
  Heiner Ackermann, Paul W. Goldberg, Vahab S. Mirrokni, Heiko Röglin, Berthold Vöcking: Uncoordinated Two-Sided Matching Markets. 92-106
• 
  Alasdair Urquhart: A Near-Optimal Separation of Regular and General Resolution. 107-121
• 
  Yuval Ishai, Jonathan Katz, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank: On Achieving the "Best of Both Worlds" in Secure Multiparty Computation. 122-141
• 
  Frédéric Magniez, Ashwin Nayak, Jérémie Roland, Miklos Santha: Search via Quantum Walk. 142-164
• 
  Ryan O'Donnell, Rocco A. Servedio: The Chow Parameters Problem. 165-199
• 
  Nitin Saxena, C. Seshadhri: An Almost Optimal Rank Bound for Depth-3 Identities. 200-224

Volume 40, Number 2, 2011

• 
  Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell, Erez Petrank: Black-Box Constructions of Protocols for Secure Computation. 225-266
• 
  Avraham Ben-Aroya, Amnon Ta-Shma: A Combinatorial Construction of Almost-Ramanujan Graphs Using the Zig-Zag Product. 267-290
• 
  Alan M. Frieze, Páll Melsted, Michael Mitzenmacher: An Analysis of Random-Walk Cuckoo Hashing. 291-308
• 
  Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard J. Karloff: Improved Approximation Algorithms for Prize-Collecting Steiner Tree and TSP. 309-332
• 
  Timothy M. Chan, Mihai Patrascu, Liam Roditty: Dynamic Connectivity: Connecting to Networks and Geometry. 333-349
• 
  Nir Ailon, Bernard Chazelle, Kenneth L. Clarkson, Ding Liu, Wolfgang Mulzer, C. Seshadhri: Self-Improving Algorithms. 350-375
• 
  Oded Goldreich, Dana Ron: Algorithmic Aspects of Property Testing in the Dense Graphs Model. 376-445
• 
  Omer Giménez, Guillem Godoy, Sebastian Maneth: Deciding Regularity of the Set of Instances of a Set of Terms with Regular Constraints is EXPTIME-Complete. 446-464
• 
  Johannes Fischer, Volker Heun: Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays. 465-492
• 
  Christian Cachin, Idit Keidar, Alexander Shraer: Fail-Aware Untrusted Storage. 493-533
• 
  Oded Goldreich, Dana Ron: On Proximity-Oblivious Testing. 534-566
• 
  Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson: Inapproximability Results for Maximum Edge Biclique, Minimum Linear Arrangement, and Sparsest Cut. 567-596

Volume 40, Number 3, 2011

• 
  Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha Riesenfeld, Elad Verbin: Sorting and Selection in Posets. 597-622
• 
  Ning Chen, Arpita Ghosh, Sergei Vassilvitskii: Optimal Envy-Free Pricing with Metric Substitutability. 623-645
• 
  Partha Niyogi, Stephen Smale, Shmuel Weinberger: A Topological View of Unsupervised Learning from Noisy Data. 646-663
• 
  Amnon Ta-Shma: Short Seed Extractors against Quantum Storage. 664-677
• 
  Elliot Anshelevich, Adriana Karagiozova: Terminal Backup, 3D Matching, and Covering Cubic Graphs. 678-708
• 
  Satyen Kale, C. Seshadhri: An Expansion Tester for Bounded Degree Graphs. 709-720
• 
  Manuel Bodirsky, Éric Fusy, Mihyun Kang, Stefan Vigerske: Boltzmann Samplers, Pólya Theory, and Cycle Pointing. 721-769
• 
  Scott Aaronson, Jeff Erickson, Mohammad Mahdian, R. Ravi, Emanuele Viola: Special Section on Foundations of Computer Science. 770
• 
  Ran Raz: A Counterexample to Strong Parallel Repetition. 771-777
• 
  Zeev Dvir, Avi Wigderson: Kakeya Sets, New Mergers, and Old Extractors. 778-792
• 
  Shiva Prasad Kasiviswanathan, Homin K. Lee, Kobbi Nissim, Sofya Raskhodnikova, Adam Smith: What Can We Learn Privately? 793-826
• 
  Mihai Patrascu: Unifying the Landscape of Cell-Probe Lower Bounds. 827-847
• 
  Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Ben Toner, Thomas Vidick: Entangled Games Are Hard to Approximate. 848-877
• 
  Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar: Beating the Random Ordering Is Hard: Every Ordering CSP Is Approximation Resistant. 878-914
• 
  Peerapong Dhangwatnotai, Shahar Dobzinski, Shaddin Dughmi, Tim Roughgarden: Truthful Approximation Schemes for Single-Parameter Agents. 915-933
• 
  Ehud Friedgut, Gil Kalai, Nathan Keller, Noam Nisan: A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives. 934-952

Volume 40, Number 4, 2011

• 
  Yuk Hei Chan, Wai Shing Fung, Lap Chi Lau, Chun Kong Yung: Degree Bounded Network Design with Metric Costs. 953-980
• 
  Daniel A. Spielman, Shang-Hua Teng: Spectral Sparsification of Graphs. 981-1025
• 
  Tamal K. Dey, Anil N. Hirani, Bala Krishnamoorthy: Optimal Homologous Cycles, Total Unimodularity, and Linear Programming. 1026-1044
• 
  Micha Sharir, Hayim Shaul: Semialgebraic Range Reporting and Emptiness Searching with Applications. 1045-1074
• 
  Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer: Testing Fourier Dimensionality and Sparsity. 1075-1100
• 
  Jin-yi Cai, Pinyan Lu, Mingji Xia: Computational Complexity of Holant Problems. 1101-1132
• 
  Uriel Feige, Vahab S. Mirrokni, Jan Vondrák: Maximizing Non-monotone Submodular Functions. 1133-1153
• 
  Zeev Dvir, Parikshit Gopalan, Sergey Yekhanin: Matching Vector Codes. 1154-1178
• 
  Peter Bürgisser, J. M. Landsberg, Laurent Manivel, Jerzy Weyman: An Overview of Mathematical Issues Arising in the Geometric Complexity Theory Approach to VP≠VNP. 1179-1209

Volume 40, Number 5, 2011

• 
  Sebastian Aland, Dominic Dumrauf, Martin Gairing, Burkhard Monien, Florian Schoppmann: Exact Price of Anarchy for Polynomial Congestion Games. 1211-1233
• 
  George B. Mertzios, Ignasi Sau, Shmuel Zaks: The Recognition of Tolerance and Bounded Tolerance Graphs. 1234-1257
• 
  Ola Svensson: Hardness of Precedence Constrained Scheduling on Identical Machines. 1258-1274
• 
  Nir Ailon, Moses Charikar: Fitting Tree Metrics: Hierarchical Clustering and Phylogeny. 1275-1291
• 
  Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, Oleg Verbitsky: Interval Graphs: Canonical Representations in Logspace. 1292-1315
• 
  James King, Erik Krohn: Terrain Guarding is NP-Hard. 1316-1339
• 
  Tao Jiang, Zevi Miller, Dan Pritikin: Near Optimal Bounds for Steiner Trees in the Hypercube. 1340-1360
• 
  Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha: Sampling and Cost-Sharing: Approximation Algorithms for Stochastic Optimization Problems. 1361-1401
• 
  Edith Cohen, Nick G. Duffield, Haim Kaplan, Carsten Lund, Mikkel Thorup: Efficient Stream Sampling for Variance-Optimal Estimation of Subset Sums. 1402-1431
• 
  Parikshit Gopalan, Venkatesan Guruswami, Prasad Raghavendra: List Decoding Tensor Products and Interleaved Codes. 1432-1462

Volume 40, Number 6, 2011

• 
  Bernhard Haeupler, Siddhartha Sen, Robert Endre Tarjan: Rank-Pairing Heaps. 1463-1485
• 
  Iftach Haitner, Danny Harnik, Omer Reingold: On the Power of the Randomized Iterate. 1486-1528
• 
  Rafael Pass, Wei-Lung Dustin Tseng, Douglas Wikström: On the Composition of Public-Coin Zero-Knowledge Protocols. 1529-1553
• 
  Patrick Briest, Piotr Krysta: Buying Cheap Is Expensive: Approximability of Combinatorial Pricing Problems. 1554-1586
• 
  Patrick Briest, Piotr Krysta, Berthold Vöcking: Approximation Techniques for Utilitarian Mechanism Design. 1587-1622
• 
  Shai Shalev-Shwartz, Ohad Shamir, Karthik Sridharan: Learning Kernel-Based Halfspaces with the 0-1 Loss. 1623-1646
• 
  Haim Kaplan, Matthew J. Katz, Gila Morgenstern, Micha Sharir: Optimal Cover of Points by Disks in a Simple Polygon. 1647-1661
• 
  Norm Ferns, Prakash Panangaden, Doina Precup: Bisimulation Metrics for Continuous Markov Decision Processes. 1662-1714
• 
  Zoya Svitkina, Lisa Fleischer: Submodular Approximation: Sampling-based Algorithms and Lower Bounds. 1715-1737
• 
  Shuchi Chawla, Cynthia Dwork, Venkat Guruswami: Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008). 1738
• 
  Gruia Calinescu, Chandra Chekuri, Martin Pál, Jan Vondrák: Maximizing a Monotone Submodular Function Subject to a Matroid Constraint. 1740-1766
• 
  Kiran S. Kedlaya, Christopher Umans: Fast Polynomial Factorization and Modular Composition. 1767-1802
• 
  Chris Peikert, Brent Waters: Lossy Trapdoor Functions and Their Applications. 1803-1844
• 
  Ilya Mironov, Moni Naor, Gil Segev: Sketching in Adversarial Environments. 1845-1870
• 
  Anup Rao: Parallel Repetition in Projection Games and a Concentration Bound. 1871-1891
• 
  Hagay Levin, Michael Schapira, Aviv Zohar: Interdomain Routing and Games. 1892-1912
• 
  Daniel A. Spielman, Nikhil Srivastava: Graph Sparsification by Effective Resistances. 1913-1926
• 
  Paul Valiant: Testing Symmetric Properties of Distributions. 1927-1968
• 
  Alexander A. Sherstov: The Pattern Matrix Method. 1969-2000

last updated on Fri May 24 06:30:56 2013 by the dblp team
data released under the ODC-BY 1.0 license
see also our legal information page