default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDSIAM Journal on Computing, Volume 38
Volume 38, Number 1, 2008
- Nir Halman:
On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model. 1-45 - Sophie Laplante, Frédéric Magniez:
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. 46-62 - Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. 63-84 - Anna Pagh, Rasmus Pagh:
Uniform Hashing in Constant Time and Optimal Space. 85-96 - Yevgeniy Dodis, Rafail Ostrovsky
, Leonid Reyzin, Adam D. Smith:
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. 97-139 - Dana Moshkovitz, Ran Raz:
Sub-Constant Error Low Degree Test of Almost-Linear Size. 140-180 - Bodo Manthey:
On Approximating Restricted Cycle Covers. 181-206 - Eldar Fischer, Arie Matsliah:
Testing Graph Isomorphism. 207-225 - Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson:
Improving the Stretch Factor of a Geometric Network by Edge Augmentation. 226-240 - Kamal Jain, Vijay V. Vazirani:
Equitable Cost Allocations via Primal--Dual-Type Algorithms. 241-256 - Mark de Berg, Chris Gray:
Vertical Ray Shooting and Computing Depth Orders for Fat Objects. 257-275 - Reuven Cohen, David Peleg:
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. 276-302 - Vasco Brattka:
Plottable Real Number Functions and the Computable Graph Theorem. 303-328 - Peter Jonsson, Fredrik Kuivinen, Gustav Nordh:
MAX ONES Generalized to Larger Domains. 329-365 - Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis:
Exponential Separation of Quantum and Classical One-Way Communication Complexity. 366-384 - Ke Chen, Sariel Har-Peled:
The Euclidean Orienteering Problem Revisited. 385-397 - János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt:
Lower Bound for the Online Bin Packing Problem with Restricted Repacking. 398-410 - Leah Epstein, Asaf Levin:
An APTAS for Generalized Cost Variable-Sized Bin Packing. 411-428 - Csaba D. Tóth:
Binary Space Partitions for Axis-Aligned Fat Rectangles. 429-447
Volume 38, Number 2, 2008
- Vladimir Trifonov:
An O(logn loglogn) Space Algorithm for Undirected st-Connectivity. 449-483 - Ben Morris:
The Mixing Time of the Thorp Shuffle. 484-504 - Noga Alon, Asaf Shapira:
Every Monotone Graph Property Is Testable. 505-522 - Saurabh Sanghvi, Salil P. Vadhan:
The Round Complexity of Two-Party Random Selection. 523-550 - Eli Ben-Sasson, Madhu Sudan:
Short PCPs with Polylog Query Complexity. 551-607 - Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng:
Lower-Stretch Spanning Trees. 608-628 - Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee:
Improved Approximation Algorithms for Minimum Weight Vertex Separators. 629-657 - Mikolaj Bojanczyk, Thomas Colcombet:
Tree-Walking Automata Do Not Recognize All Regular Languages. 658-701 - Rafael Pass, Alon Rosen:
New and Improved Constructions of Nonmalleable Cryptographic Protocols. 702-752
Volume 38, Number 3, 2008
- Yaoyun Shi, Yufan Zhu:
Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement. 753-766 - Anil Maheshwari, Norbert Zeh:
I/O-Efficient Planar Separators. 767-801 - Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang:
Approximate Shortest Paths in Anisotropic Regions. 802-824 - Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio:
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover. 825-840 - Marcelo Arenas, Wenfei Fan, Leonid Libkin:
On the Complexity of Verifying Consistency of XML Specifications. 841-880 - Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen:
Competitive Online Approximation of the Optimal Search Ratio. 881-898 - Boris Aronov, Sariel Har-Peled:
On Approximating the Depth and Related Problems. 899-921 - Àngel J. Gil, Miki Hermann, Gernot Salzer, Bruno Zanuttini:
Efficient Algorithms for Description Problems over Finite Totally Ordered Domains. 922-945 - C. Thach Nguyen, Jian Shen, Minmei Hou, Li Sheng, Webb Miller, Louxin Zhang:
Approximating the Spanning Star Forest Problem and Its Application to Genomic Sequence Alignment. 946-962 - Igor L. Markov, Yaoyun Shi:
Simulating Quantum Computation by Contracting Tensor Networks. 963-981 - Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin:
Efficient Colored Orthogonal Range Counting. 982-1011 - Petr Hlinený, Sang-il Oum:
Finding Branch-Decompositions and Rank-Decompositions. 1012-1032 - Parikshit Gopalan:
Query-Efficient Algorithms for Polynomial Interpolation over Composites. 1033-1057 - Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger:
Exact Algorithms for Treewidth and Minimum Fill-In. 1058-1079 - Jack H. Lutz, Elvira Mayordomo:
Dimensions of Points in Self-Similar Fractals. 1080-1112 - Jordi Levy, Manfred Schmidt-Schauß, Mateu Villaret:
The Complexity of Monadic Second-Order Unification. 1113-1140 - Ravindran Kannan, Hadi Salmasian, Santosh S. Vempala:
The Spectral Method for General Mixture Models. 1141-1156 - Nikhil Bansal, Don Coppersmith, Maxim Sviridenko:
Improved Approximation Algorithms for Broadcast Scheduling. 1157-1174 - Ketan Mulmuley, Milind A. Sohoni:
Geometric Complexity Theory II: Towards Explicit Obstructions for Embeddings among Class Varieties. 1175-1206
Volume 38, Number 4, 2008
- Dorit Aharonov, Michael Ben-Or:
Fault-Tolerant Quantum Computation with Constant Error Rate. 1207-1282 - Sanjay Jain, Frank Stephan:
Mitotic Classes in Inductive Inference. 1283-1299 - Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung:
On Monotone Formula Composition of Perfect Zero-Knowledge Languages. 1300-1329 - Jon M. Kleinberg, Mark Sandler, Aleksandrs Slivkins:
Network Failure Detection and Graph Connectivity. 1330-1346 - Michael Alekhnovich, Alexander A. Razborov:
Resolution Is Not Automatizable Unless W[P] Is Tractable. 1347-1363 - Albert Atserias, Anuj Dawar, Martin Grohe:
Preservation under Extensions on Well-Behaved Finite Structures. 1364-1381 - Dániel Marx:
Closest Substring Problems with Small Distances. 1382-1410 - Ivan D. Baev, Rajmohan Rajaraman, Chaitanya Swamy:
Approximation Algorithms for Data Placement Problems. 1411-1429 - Ramesh Hariharan, Telikepalli Kavitha, Kurt Mehlhorn:
Faster Algorithms for Minimum Cycle Basis in Directed Graphs. 1430-1447 - Subhash Khot, Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. 1448-1463 - Erik D. Demaine, Uriel Feige, MohammadTaghi Hajiaghayi, Mohammad R. Salavatipour:
Combination Can Be Hard: Approximability of the Unique Coverage Problem. 1464-1483 - Shuji Kijima, Tomomi Matsui:
Approximation Algorithm and Perfect Sampler for Closed Jackson Networks with Single Servers. 1484-1503 - Lusheng Wang, Yu Lin, Xiaowen Liu:
Approximation Algorithms for Biclustering Problems. 1504-1518 - Marcin Jurdzinski, Mike Paterson, Uri Zwick:
A Deterministic Subexponential Algorithm for Solving Parity Games. 1519-1532 - Adam L. Buchsbaum, Loukas Georgiadis, Haim Kaplan, Anne Rogers, Robert Endre Tarjan, Jeffery R. Westbrook:
Linear-Time Algorithms for Dominators and Other Path-Evaluation Problems. 1533-1573 - Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal, Corentin Travers:
The Combined Power of Conditions and Information on Failures to Solve Asynchronous Set Agreement. 1574-1601 - Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden:
The Price of Stability for Network Design with Fair Cost Allocation. 1602-1623 - Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. 1624-1647 - Adam Meyerson, Kamesh Munagala, Serge A. Plotkin:
Cost-Distance: Two Metric Network Design. 1648-1659
Volume 38, Number 5, 2008
- Boaz Barak, Oded Goldreich:
Universal Arguments and their Applications. 1661-1694 - Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, Ronald de Wolf:
Exponential Separation for One-Way Quantum Communication Complexity, with Applications to Cryptography. 1695-1708 - Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang:
Graph Distances in the Data-Stream Model. 1709-1727 - Amos Beimel, Paz Carmi, Kobbi Nissim, Enav Weinreb:
Private Approximation of Search Problems. 1728-1760 - Yuval Emek, David Peleg:
Approximating Minimum Max-Stretch Spanning Trees on Unweighted Graphs. 1761-1781
Volume 38, Number 5, 2009
- Libor Barto, Marcin Kozik, Todd Niven:
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell). 1782-1802 - Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid:
Spanners of Complete k-Partite Geometric Graphs. 1803-1820 - GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski:
Profiles of Tries. 1821-1880 - Umberto Straccia, Manuel Ojeda-Aciego, Carlos Viegas Damásio:
On Fixed-Points of Multivalued Functions on Complete Lattices and Their Application to Generalized Logic Programs. 1881-1911 - Ulrich Schmid, Bettina Weiss, Idit Keidar:
Impossibility Results and Lower Bounds for Consensus under Link Failures. 1912-1951 - Kiran S. Kedlaya, Sergey Yekhanin:
Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. 1952-1969 - Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Weighted Boolean #CSP. 1970-1986 - Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen:
On the Complexity of Numerical Analysis. 1987-2006 - Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle:
Interval Completion Is Fixed Parameter Tractable. 2007-2020 - Wouter Gelade, Wim Martens, Frank Neven:
Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. 2021-2043 - Sudipto Guha, Andrew McGregor:
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. 2044-2059 - Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney:
Sampling Algorithms and Coresets for $\ellp Regression. 2060-2078 - Holger Spakowski, Rahul Tripathi:
Hierarchical Unambiguity. 2079-2112
Volume 38, Number 6, 2009
- Alexander A. Sherstov:
SeparatingAC0 from Depth-2 Majority Circuits. 2113-2129 - Amir Shpilka:
Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. 2130-2161 - Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. 2162-2178 - Mee Yee Chan, Wun-Tat Chan, Francis Y. L. Chin, Stanley P. Y. Fung, Ming-Yang Kao:
Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops. 2179-2197 - Jing Xiao, Lan Liu, Lirong Xia, Tao Jiang:
Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations. 2198-2219 - Louay M. J. Bazzi:
Polylogarithmic Independence Can Fool DNF Formulas. 2220-2272 - Susanne Albers:
On the Value of Coordination in Network Design. 2273-2302 - T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Aleksandrs Slivkins:
Metric Embeddings with Relaxed Guarantees. 2303-2329 - Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou:
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. 2330-2355 - Leonard M. Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, Petr Sosík:
The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly. 2356-2381 - David J. Aldous, Charles Bordenave, Marc Lelarge:
Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions. 2382-2410 - Luc Devroye, James King, Colin McDiarmid:
Random Hyperplane Search Trees. 2411-2425 - Sudipto Guha, Adam Meyerson, Kamesh Munagala:
A Constant Factor Approximation for the Single Sink Edge Installation Problem. 2426-2442 - Marcin Kozik:
A 2EXPTIME Complete Varietal Membership Problem. 2443-2467 - Baruch Awerbuch, Rohit Khandekar:
Stateless Distributed Gradient Descent for Positive Linear Programs. 2468-2486 - Robert Krauthgamer, Yuval Rabani:
Improved Lower Bounds for Embeddings intoL1$. 2487-2498 - Artur Czumaj, Asaf Shapira, Christian Sohler:
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. 2499-2510
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 2025-11-22 03:46 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:
