Span Programs are Equivalent to Quantum Query Algorithms

JOURNAL ARTICLE published January 2014 in SIAM Journal on Computing

Authors: Ben W. Reichardt

Partially Symmetric Functions Are Efficiently Isomorphism Testable

JOURNAL ARTICLE published January 2015 in SIAM Journal on Computing

Authors: Eric Blais | Amit Weinstein | Yuichi Yoshida

On Testing Convexity and Submodularity

JOURNAL ARTICLE published January 2003 in SIAM Journal on Computing

Authors: Michal Parnas | Dana Ron | Ronitt Rubinfeld

A Note on the Height of Suffix Trees

JOURNAL ARTICLE published February 1992 in SIAM Journal on Computing

Authors: Luc Devroye | Wojciech Szpankowski | Bonita Rais

A Shortest-Path Algorithm with Expected Time $O(n^2 log nlog ^ * n)$

JOURNAL ARTICLE published August 1983 in SIAM Journal on Computing

Authors: Peter A. Bloniarz

A Fast Algorithm For Optimum Height-Limited Alphabetic Binary Trees

JOURNAL ARTICLE published December 1994 in SIAM Journal on Computing

Authors: Lawrence L. Larmore | Teresa M. Przytycka

Information Transfer under Different Sets of Protocols

JOURNAL ARTICLE published November 1984 in SIAM Journal on Computing

Authors: J. Ja’Ja’ | V. K. Prasanna Kumar | J. Simon

Learning Integer Lattices

JOURNAL ARTICLE published April 1992 in SIAM Journal on Computing

Authors: David Helmbold | Robert Sloan | Manfred K. Warmuth

A Note on Spira’s Algorithm for the All-Pairs Shortest-Path Problem

JOURNAL ARTICLE published December 1977 in SIAM Journal on Computing

Authors: John S. Carson | Averill M. Law

Efficient Ordering of Hash Tables

JOURNAL ARTICLE published August 1979 in SIAM Journal on Computing

Authors: Gaston H. Gonnet | J. Ian Munro

Worst-Case and Smoothed Analysis of the ICP Algorithm, with an Application to the k-Means Method

JOURNAL ARTICLE published January 2009 in SIAM Journal on Computing

Authors: David Arthur | Sergei Vassilvitskii

The Probabilistic Relationship Between the Assignment and Asymmetric Traveling Salesman Problems

JOURNAL ARTICLE published January 2007 in SIAM Journal on Computing

Authors: Alan Frieze | Gregory B. Sorkin

Effective Computations on Sliding Windows

JOURNAL ARTICLE published January 2010 in SIAM Journal on Computing

Authors: Vladimir Braverman | Rafail Ostrovsky

Checking Approximate Computations of Polynomials and Functional Equations

JOURNAL ARTICLE published January 2001 in SIAM Journal on Computing

Authors: Funda Ergün | S. Ravi Kumar | Ronitt Rubinfeld

Dynamic Programming Optimization over Random Data: The Scaling Exponent for Near-Optimal Solutions

JOURNAL ARTICLE published January 2009 in SIAM Journal on Computing

Authors: David J. Aldous | Charles Bordenave | Marc Lelarge

Envy-Free Makespan Approximation

JOURNAL ARTICLE published January 2012 in SIAM Journal on Computing

Authors: Edith Cohen | Michal Feldman | Amos Fiat | Haim Kaplan | Svetlana Olonetsky

On Minimal-Time Solutions of Firing Squad Synchronization Problems for Networks

JOURNAL ARTICLE published January 2012 in SIAM Journal on Computing

Authors: Darin Goldstein | Kojiro Kobayashi

The Equivalence Problem for Single-Valued Two-Way Transducers (on NPDTOL Languages) is Decidable

JOURNAL ARTICLE published April 1987 in SIAM Journal on Computing

Authors: Karel Culik, II | Juhani Karhumäki

A New Approach to Formal Language Theory by Kolmogorov Complexity

JOURNAL ARTICLE published April 1995 in SIAM Journal on Computing

Authors: Ming Li | Paul Vitányi

The Power of Strong Fourier Sampling: Quantum Algorithms for Affine Groups and Hidden Shifts

JOURNAL ARTICLE published January 2007 in SIAM Journal on Computing

Authors: Cristopher Moore | Daniel Rockmore | Alexander Russell | Leonard J. Schulman