ISSN: 0097-5397    Frecuencia: 4   Formato: Impresa

Tablas de contenido
Skip Navigation Links.  
19 artículos asociados 
Volumen 38 Número 6 Parte 0 Año 2009

Separating ${AC}^0$ from Depth-2 Majority Circuits
Alexander A. Sherstov
Pág. 2113 - 2129  

Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates
Amir Shpilka
Pág. 2130 - 2161  

Breaking a Time-and-Space Barrier in Constructing Full-Text Indices
Wing-Kai Hon, Kunihiko Sadakane, and Wing-Kin Sung
Pág. 2162 - 2178  

Linear-Time Haplotype Inference on Pedigrees without Recombinations and Mating Loops
Mee Yee Chan, Wun-Tat Chan, Francis Y. L. Chin, Stanley P. Y. Fung, and Ming-Yang Kao
Pág. 2179 - 2197  

Efficient Algorithms for Reconstructing Zero-Recombinant Haplotypes on a Pedigree Based on Fast Elimination of Redundant Linear Equations
Jing Xiao, Lan Liu, Lirong Xia, and Tao Jiang
Pág. 2198 - 2219  

Polylogarithmic Independence Can Fool DNF Formulas
Louay M. J. Bazzi
Pág. 2220 - 2272  

On the Value of Coordination in Network Design
Susanne Albers
Pág. 2273 - 2302  

Metric Embeddings with Relaxed Guarantees
T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon Kleinberg, and Aleksandrs Slivkins
Pág. 2303 - 2329  

The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
Parikshit Gopalan, Phokion G. Kolaitis, Elitza Maneva, and Christos H. Papadimitriou
Pág. 2330 - 2355  

The Undecidability of the Infinite Ribbon Problem: Implications for Computing by Self-Assembly
Leonard Adleman, Jarkko Kari, Lila Kari, Dustin Reishus, and Petr Sosik
Pág. 2356 - 2381  

Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions
David J. Aldous, Charles Bordenave, and Marc Lelarge
Pág. 2382 - 2410  

Random Hyperplane Search Trees
Luc Devroye, James King, and Colin McDiarmid
Pág. 2411 - 2425  

A Constant Factor Approximation for the Single Sink Edge Installation Problem
Sudipto Guha, Adam Meyerson, and Kamesh Munagala
Pág. 2426 - 2442  

A 2EXPTIME Complete Varietal Membership Problem
Marcin Kozik
Pág. 2443 - 2467  

Stateless Distributed Gradient Descent for Positive Linear Programs
Baruch Awerbuch and Rohit Khandekar
Pág. 2468 - 2486  

Improved Lower Bounds for Embeddings into $L_1$
Robert Krauthgamer and Yuval Rabani
Pág. 2487 - 2498  

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
Artur Czumaj, Asaf Shapira, and Christian Sohler
Pág. 2499 - 2510  

Size-Space Tradeoffs for Resolution
Eli Ben-Sasson
Pág. 2511 - 2525  

Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
Jianer Chen, Joachim Kneis, Songjian Lu, Daniel Mölle, Stefan Richter, Peter Rossmanith, Sing-Hoi Sze, and Fenghui Zhang
Pág. 2526 - 2547