default search action
SIAM Journal on Computing, Volume 40
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
The Complexity of Early Deciding Set Agreement. 63-78 - Elad Hazan
How Hard Is It to Approximate the Best Nash Equilibrium? 79-91 - Heiner Ackermann, Paul W. Goldberg
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
On Achieving the "Best of Both Worlds" in Secure Multiparty Computation. 122-141 - Frédéric Magniez, Ashwin Nayak, Jérémie Roland
Search via Quantum Walk. 142-164 - Ryan O'Donnell, Rocco A. Servedio:
The Chow Parameters Problem. 165-199 - Nitin Saxena
An Almost Optimal Rank Bound for Depth-3 Identities. 200-224
Volume 40, Number 2, 2011
- Iftach Haitner, Yuval Ishai, Eyal Kushilevitz, Yehuda Lindell
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
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
Self-Improving Algorithms. 350-375 - Oded Goldreich
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
On Proximity-Oblivious Testing. 534-566 - Christoph Ambühl, Monaldo Mastrolilli
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
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
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
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 D. Smith:
What Can We Learn Privately? 793-826 - Mihai Patrascu:
Unifying the Landscape of Cell-Probe Lower Bounds. 827-847 - Julia Kempe
Entangled Games Are Hard to Approximate. 848-877 - Venkatesan Guruswami, Johan Håstad
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
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
Testing Fourier Dimensionality and Sparsity. 1075-1100 - Jin-yi Cai, Pinyan Lu
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
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
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
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
Rank-Pairing Heaps. 1463-1485 - Iftach Haitner, Danny Harnik, Omer Reingold:
On the Power of the Randomized Iterate. 1486-1528 - Rafael Pass
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, Venkatesan Guruswami:
Special Section on the Fortieth Annual ACM Symposium On Theory Of Computing (STOC 2008). 1738 - Gruia Calinescu
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
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
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-12-12 20:59 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: