default search action
SIAM Journal on Computing, Volume 43
Volume 43, Number 1, 2014
- Katalin Friedl, Gábor Ivanyos
, Frédéric Magniez, Miklos Santha, Pranab Sen:
Hidden Translation and Translating Coset in Quantum Computing. 1-24 - Arman Yousefi, Neal E. Young
On a Linear Program for Minimum-Weight Triangulation. 25-51 - Telikepalli Kavitha:
A Size-Popularity Tradeoff in the Stable Marriage Problem. 52-71 - Leonid Barenboim, Michael Elkin, Fabian Kuhn:
Distributed (Delta+1)-Coloring in Linear (in Delta) Time. 72-95 - René Sitters:
The Generalized Work Function Algorithm Is Competitive for the Generalized 2-Server Problem. 96-125 - Sungjin Im, Benjamin Moseley, Kirk Pruhs:
Online Scheduling with General Cost Functions. 126-143 - J. M. Landsberg:
New Lower Bounds for the Rank of Matrix Multiplication. 144-149 - Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal, Rafail Ostrovsky, Christian Schaffner
Position-Based Quantum Cryptography: Impossibility and Constructions. 150-178 - Johan Håstad
On the NP-Hardness of Max-Not-2. 179-193 - Moshe Babaioff, Yogeshwer Sharma, Aleksandrs Slivkins:
Characterizing Truthful Multi-armed Bandit Mechanisms. 194-230 - Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio
Average Sensitivity and Noise Sensitivity of Polynomial Threshold Functions. 231-253 - Johan Håstad
Erratum: Polynomial Time Algorithms for Finding Integer Relations Among Real Numbers. 254
- Lap Chi Lau, Tal Malkin, Ryan O'Donnell, Luca Trevisan
Special Section on the Fifty-First Annual IEEE Symposium on Foundations of Computer Science (FOCS 2010). 255 - Benjamin Rossman:
The Monotone Complexity of k-Clique on Random Graphs. 256-279 - Andreas Björklund:
Determinant Sums for Undirected Hamiltonicity. 280-299 - Mihai Patrascu, Liam Roditty:
Distance Oracles beyond the Thorup-Zwick Bound. 300-311 - Shaddin Dughmi, Tim Roughgarden:
Black-Box Randomized Reductions in Algorithmic Mechanism Design. 312-336 - Ioannis Koutis
Approaching Optimality for Solving SDD Linear Systems. 337-354
Volume 43, Number 2, 2014
- Dániel Marx, Igor Razgon:
Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset. 355-388 - Iftach Haitner, Eran Omri
Coin Flipping with Constant Bias Implies One-Way Functions. 389-409 - Siu-Wing Cheng
Approximate Shortest Descending Paths. 410-428 - Pankaj K. Agarwal, Rinat Ben Avraham, Haim Kaplan, Micha Sharir:
Computing the Discrete Fréchet Distance in Subquadratic Time. 429-449 - Gil Cohen, Ran Raz
Nonmalleable Extractors with Short Seeds and Applications to Privacy Amplification. 450-476 - Hsueh-I Lu:
Linear-Time Compression of Bounded-Genus Graphs into Information-Theoretically Optimal Number of Bits. 477-496 - Alan M. Frieze
Expanders via Random Spanning Trees. 497-513 - Yuval Filmus, Justin Ward:
Monotone Submodular Maximization over a Matroid via Non-Oblivious Local Search. 514-542 - Boris Aronov
Improved Bounds for the Union of Locally Fat Objects in the Plane. 543-572 - Andrei A. Bulatov, Dániel Marx:
Constraint Satisfaction Parameterized by Solution Size. 573-616 - Kenneth L. Clarkson, Wolfgang Mulzer
Self-Improving Algorithms for Coordinatewise Maxima and Convex Hulls. 617-653
- Eli Ben-Sasson, Rafail Ostrovsky:
Special Section on the Fifty-Second IEEE Annual Symposium on Foundations of Computer Science (FOCS 2011). 654 - Emanuele Viola:
Extractors for Circuit Sources. 655-672 - Kasper Green Larsen:
On Range Searching in the Group Model and Combinatorial Discrepancy. 673-686 - Christos Boutsidis, Petros Drineas
Near-Optimal Column-Based Matrix Reconstruction. 687-717 - Timon Hertli:
3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. 718-729 - Madhur Tulsiani, Julia Wolf:
Quadratic Goldreich-Levin Theorems. 730-766 - Paul S. Bonsma, Jens Schulz, Andreas Wiese
A Constant-Factor Approximation Algorithm for Unsplittable Flow on Paths. 767-799 - Yevgeniy Dodis, Xin Li, Trevor D. Wooley
Privacy Amplification and Nonmalleable Extractors Via Character Sums. 800-830 - Zvika Brakerski, Vinod Vaikuntanathan:
Efficient Fully Homomorphic Encryption from (Standard) $\mathsf{LWE}$. 831-871 - Nikhil Bansal, Uriel Feige, Robert Krauthgamer
Min-Max Graph Partitioning and Small Set Expansion. 872-904 - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
How to Garble Arithmetic Circuits. 905-929 - Saeed Alaei
Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. 930-972
Volume 43, Number 3, 2014
- Mark Braverman, Anup Rao, Ran Raz
Pseudorandom Generators for Regular Branching Programs. 973-986 - Michael Ben-Or
Quantum Multiprover Interactive Proofs with Communicating Provers. 987-1011 - Emanuel Kieronski
Two-Variable First-Order Logic with Equivalence Closure. 1012-1063 - Anna Huber, Andrei A. Krokhin
Skew Bisubmodularity and Valued CSPs. 1064-1084 - Pablo Barceló, Leonid Libkin
Efficient Approximations of Conjunctive Queries. 1085-1130 - Scott Aaronson, Andrew Drucker:
A Full Characterization of Quantum Advice. 1131-1183 - Subhash Khot, Preyas Popat, Nisheeth K. Vishnoi:
Almost Polynomial Factor Hardness for Closest Vector Problem with Preprocessing. 1184-1205 - Ben W. Reichardt:
Span Programs are Equivalent to Quantum Query Algorithms. 1206-1219 - Matthias Englert, Deniz Özmen, Matthias Westermann:
The Power of Reordering for Online Minimum Makespan Scheduling. 1220-1237
Volume 43, Number 4, 2014
- Matthias Englert, Anupam Gupta, Robert Krauthgamer
Vertex Sparsifiers: New Results from Old Techniques. 1239-1262 - Fabrizio Grandoni
Utilitarian Mechanism Design for Multiobjective Optimization. 1263-1290 - Nishanth Chandran, Vipul Goyal, Ryan Moriarty, Rafail Ostrovsky:
Position-Based Cryptography. 1291-1341 - Joseph Cheriyan, László A. Végh
Approximating Minimum-Cost k-Node Connected Subgraphs via Independence-Free Graphs. 1342-1362 - Dror Aiger, Haim Kaplan, Micha Sharir:
Reporting Neighbors in High-Dimensional Euclidean Space. 1363-1395 - Amihood Amir, Gianni Franceschini, Roberto Grossi, Tsvi Kopelowitz, Moshe Lewenstein, Noa Lewenstein:
Managing Unbounded-Length Keys in Comparison-Driven Data Structures with Applications to Online Indexing. 1396-1416 - Hamed Hatami, Shachar Lovett
Correlation Testing for Affine Invariant Properties on 픽pn in the High Error Regime. 1417-1455 - Amin Coja-Oghlan, Alan M. Frieze
Analyzing Walksat on Random Formulas. 1456-1485 - Sariel Har-Peled
Down the Rabbit Hole: Robust Proximity Search and Density Estimation in Sublinear Space. 1486-1511
Volume 43, Number 5, 2014
- Hai Brenner, Kobbi Nissim
Impossibility of Differentially Private Universally Optimal Mechanisms. 1513-1540 - Fedor V. Fomin
Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. 1541-1563 - Sebastian Faust, Tal Rabin, Leonid Reyzin, Eran Tromer, Vinod Vaikuntanathan:
Protecting Circuits from Computationally Bounded and Noisy Leakage. 1564-1614 - Flavio Chierichetti, Jon M. Kleinberg:
Voting with Limited Information and Many Alternatives. 1615-1653 - Abhishek Bhowmick, Zeev Dvir, Shachar Lovett
New Bounds for Matching Vector Families. 1654-1683 - Nikhil Bansal, Kirk Pruhs:
The Geometry of Scheduling. 1684-1698 - Johan Håstad
On the Correlation of Parity and Small-Depth Circuits. 1699-1708 - Thomas Watson:
Time Hierarchies for Sampling Distributions. 1709-1727 - Martin Cadek
Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension. 1728-1780 - Gonzalo Navarro, Yakov Nekrich
Optimal Dynamic Sequence Representations. 1781-1806 - Michael Dinitz
Matroid Secretary for Regular and Decomposable Matroids. 1807-1830
Volume 43, Number 6, 2014
- Chandra Chekuri, Jan Vondrák, Rico Zenklusen:
Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. 1831-1879 - Frédéric Magniez, Claire Mathieu, Ashwin Nayak:
Recognizing Well-Parenthesized Expressions in the Streaming Model. 1880-1905 - Flavio Chierichetti, Jon M. Kleinberg, Alessandro Panconesi:
How to Schedule a Cascade in an Arbitrary Graph. 1906-1920 - Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Computing the Sign of the Tutte Polynomial. 1921-1952
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-26 00:54 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: