| Hits ?▲ |
Authors |
Title |
Venue |
Year |
Link |
Author keywords |
| 1 | Robert Krauthgamer, Yuval Rabani |
Improved Lower Bounds for Embeddings intoL1$.   |
SIAM J. Comput.  |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Amir Shpilka |
Interpolation of Depth-3 Arithmetic Circuits with Two Multiplication Gates. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Wouter Gelade, Wim Martens, Frank Neven |
Optimizing Schema Languages for XML: Numerical Constraints and Interleaving. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Anirban Dasgupta, Petros Drineas, Boulos Harb, Ravi Kumar, Michael W. Mahoney |
Sampling Algorithms and Coresets for $\ellp Regression. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Kiran S. Kedlaya, Sergey Yekhanin |
Locally Decodable Codes from Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Artur Czumaj, Asaf Shapira, Christian Sohler |
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Sudipto Guha, Adam Meyerson, Kamesh Munagala |
A Constant Factor Approximation for the Single Sink Edge Installation Problem. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Luc Devroye, James King, Colin McDiarmid |
Random Hyperplane Search Trees. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Holger Spakowski, Rahul Tripathi |
Hierarchical Unambiguity. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan, Phokion G. Kolaitis, Elitza N. Maneva, Christos H. Papadimitriou |
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Ulrich Schmid, Bettina Weiss, Idit Keidar |
Impossibility Results and Lower Bounds for Consensus under Link Failures. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Prosenjit Bose, Paz Carmi, Mathieu Couture, Anil Maheshwari, Pat Morin, Michiel H. M. Smid |
Spanners of Complete k-Partite Geometric Graphs. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Alexander A. Sherstov |
SeparatingAC0 from Depth-2 Majority Circuits. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Sudipto Guha, Andrew McGregor |
Stream Order and Order Statistics: Quantile Estimation in Random-Order Streams. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Marcin Kozik |
A 2EXPTIME Complete Varietal Membership Problem. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | 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). |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Aleksandrs Slivkins |
Metric Embeddings with Relaxed Guarantees. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | GaHyun Park, Hsien-Kuei Hwang, Pierre Nicodème, Wojciech Szpankowski |
Profiles of Tries. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | David J. Aldous, Charles Bordenave, Marc Lelarge |
Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
On the Complexity of Numerical Analysis. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Louay M. J. Bazzi |
Polylogarithmic Independence Can Fool DNF Formulas. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung |
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Susanne Albers |
On the Value of Coordination in Network Design. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Yngve Villanger, Pinar Heggernes, Christophe Paul, Jan Arne Telle |
Interval Completion Is Fixed Parameter Tractable. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum |
The Complexity of Weighted Boolean CSP. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Baruch Awerbuch, Rohit Khandekar |
Stateless Distributed Gradient Descent for Positive Linear Programs. |
SIAM J. Comput. |
2009 |
DBLP DOI BibTeX RDF |
|
| 1 | Rudolf Fleischer, Thomas Kamphans, Rolf Klein, Elmar Langetepe, Gerhard Trippen |
Competitive Online Approximation of the Optimal Search Ratio. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Leah Epstein, Asaf Levin |
An APTAS for Generalized Cost Variable-Sized Bin Packing. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Anna Pagh, Rasmus Pagh |
Uniform Hashing in Constant Time and Optimal Space. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Peter Jonsson, Fredrik Kuivinen, Gustav Nordh |
MAX ONES Generalized to Larger Domains. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | 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. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Àngel J. Gil, Miki Hermann, Gernot Salzer, Bruno Zanuttini |
Efficient Algorithms for Description Problems over Finite Totally Ordered Domains. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dana Moshkovitz, Ran Raz |
Sub-Constant Error Low Degree Test of Almost-Linear Size. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | János Balogh, József Békési, Gábor Galambos, Gerhard Reinelt |
Lower Bound for the Online Bin Packing Problem with Restricted Repacking. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Anil Maheshwari, Norbert Zeh |
I/O-Efficient Planar Separators. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Reuven Cohen, David Peleg |
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Mohammad Farshi, Panos Giannopoulos, Joachim Gudmundsson |
Improving the Stretch Factor of a Geometric Network by Edge Augmentation. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks |
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Kamal Jain, Vijay V. Vazirani |
Equitable Cost Allocations via Primal--Dual-Type Algorithms. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis |
Exponential Separation of Quantum and Classical One-Way Communication Complexity. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Fabrizio Grandoni, Jochen Könemann, Alessandro Panconesi, Mauro Sozio |
A Primal-Dual Bicriteria Distributed Algorithm for Capacitated Vertex Cover. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nir Halman |
On the Algorithmic Aspects of Discrete and Lexicographic Helly-Type Theorems and the Discrete LP-Type Model. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ke Chen, Sariel Har-Peled |
The Euclidean Orienteering Problem Revisited. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Yevgeniy Dodis, Rafail Ostrovsky, Leonid Reyzin, Adam Smith |
Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Philip N. Klein |
A Linear-Time Approximation Scheme for TSP in Undirected Planar Graphs with Edge-Weights. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Navin Goyal, Guy Kindler, Michael E. Saks |
Lower Bounds for the Noisy Broadcast Problem. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Irit Dinur, Éva Tardos |
Special Issue on Foundations of Computer Science. |
SIAM J. Comput. |
2008 |
DBLP BibTeX RDF |
|
| 1 | Ivona Bezáková, Daniel Stefankovic, Vijay V. Vazirani, Eric Vigoda |
Accelerating Simulated Annealing for the Permanent and Combinatorial Counting Problems. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Asaf Shapira |
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Liam Roditty, Uri Zwick |
Improved Dynamic Reachability Algorithms for Directed Graphs. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Rafael Pass, Alon Rosen |
Concurrent Nonmalleable Commitments. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Cristopher Moore, Alexander Russell, Leonard J. Schulman |
The Symmetric Group Defies Strong Fourier Sampling. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, Rocco A. Servedio |
Agnostically Learning Halfspaces. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Camil Demetrescu, Mikkel Thorup, Rezaul Alam Chowdhury, Vijaya Ramachandran |
Oracles for Distances Avoiding a Failed Node or Link. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Hagit Attiya, David Hay |
Randomization Does Not Reduce the Average Delay in Parallel Packet Switches. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Hubie Chen |
The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Christian Glaßer, Aduri Pavan, Alan L. Selman, Liyu Zhang |
Splitting NP-Complete Sets. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Andrew V. Goldberg |
A Practical Shortest Path Algorithm with Linear Expected Time. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ofer Dekel, Shai Shalev-Shwartz, Yoram Singer |
The Forgetron: A Kernel-Based Perceptron on a Budget. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig |
Quantum Property Testing. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Elliot Anshelevich, David Kempe, Jon M. Kleinberg |
Stability of Load Balancing Algorithms in Dynamic Adversarial Systems. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Leslie G. Valiant |
Holographic Algorithms. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ho-Leung Chan, Tak Wah Lam, Kin-Shing Liu |
Extra Unit-Speed Machines Are Almost as Powerful as Speedy Machines for Flow Time Scheduling. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ivan Damgård, Serge Fehr, Louis Salvail, Christian Schaffner |
Cryptography in the Bounded-Quantum-Storage Model. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | John Augustine, Sandy Irani, Chaitanya Swamy |
Optimal Power-Down Strategies. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Penny E. Haxell, Brendan Nagle, Vojtech Rödl |
An Algorithmic Version of the Hypergraph Regularity Method. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Karl Rubin, Alice Silverberg |
Compression in Finite Fields and Torus-Based Cryptography. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Aaron Archer, Asaf Levin, David P. Williamson |
A Faster, Better Approximation Algorithm for the Minimum Latency Problem. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jochen Könemann, Stefano Leonardi, Guido Schäfer, Stefan H. M. van Zwam |
A Group-Strategyproof Cost Sharing Mechanism for the Steiner Forest Game. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Bradford G. Nickerson, Qingxiu Shi |
On k-d Range Search with Patricia Tries. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Jon Feldman, Ryan O'Donnell, Rocco A. Servedio |
Learning Mixtures of Product Distributions over Discrete Domains. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eldar Fischer, Arie Matsliah |
Testing Graph Isomorphism. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Mark de Berg, Chris Gray |
Vertical Ray Shooting and Computing Depth Orders for Fat Objects. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Sophie Laplante, Frédéric Magniez |
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Yaoyun Shi, Yufan Zhu |
Tensor Norms and the Classical Communication Complexity of Nonlocal Quantum Measurement. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Boris Aronov, Sariel Har-Peled |
On Approximating the Depth and Related Problems. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Vasco Brattka |
Plottable Real Number Functions and the Computable Graph Theorem. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Csaba D. Tóth |
Binary Space Partitions for Axis-Aligned Fat Rectangles. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Siu-Wing Cheng, Hyeon-Suk Na, Antoine Vigneron, Yajun Wang |
Approximate Shortest Paths in Anisotropic Regions. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Marcelo Arenas, Wenfei Fan, Leonid Libkin |
On the Complexity of Verifying Consistency of XML Specifications. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Bodo Manthey |
On Approximating Restricted Cycle Covers. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Dorit Aharonov, Michael Ben-Or |
Fault-Tolerant Quantum Computation with Constant Error Rate. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Sanjay Jain, Frank Stephan |
Mitotic Classes in Inductive Inference. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano, Moti Yung |
On Monotone Formula Composition of Perfect Zero-Knowledge Languages. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Alekhnovich, Alexander A. Razborov |
Resolution Is Not Automatizable Unless W[P] Is Tractable. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Eli Ben-Sasson, Madhu Sudan |
Short PCPs with Polylog Query Complexity. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Ravindran Kannan, Hadi Salmasian, Santosh Vempala |
The Spectral Method for General Mixture Models. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Saurabh Sanghvi, Salil P. Vadhan |
The Round Complexity of Two-Party Random Selection. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Michael Elkin, Yuval Emek, Daniel A. Spielman, Shang-Hua Teng |
Lower-Stretch Spanning Trees. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Vladimir Trifonov |
An O(logn loglogn) Space Algorithm for Undirected st-Connectivity. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Noga Alon, Asaf Shapira |
Every Monotone Graph Property Is Testable. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Mikolaj Bojanczyk, Thomas Colcombet |
Tree-Walking Automata Do Not Recognize All Regular Languages. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Parikshit Gopalan |
Query-Efficient Algorithms for Polynomial Interpolation over Composites. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Nikhil Bansal, Don Coppersmith, Maxim Sviridenko |
Improved Approximation Algorithms for Broadcast Scheduling. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Fedor V. Fomin, Dieter Kratsch, Ioan Todinca, Yngve Villanger |
Exact Algorithms for Treewidth and Minimum Fill-In. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
| 1 | Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee |
Improved Approximation Algorithms for Minimum Weight Vertex Separators. |
SIAM J. Comput. |
2008 |
DBLP DOI BibTeX RDF |
|
![[Valid RSS]](Pics/valid-rss.png "Validate my RSS feed")