On Sets with Efficient Implicit Membership Tests

JOURNAL ARTICLE published December 1991 in SIAM Journal on Computing

Authors: Lane A. Hemachandra | Albrecht Hoene

Filtering Search: A New Approach to Query-Answering

JOURNAL ARTICLE published August 1986 in SIAM Journal on Computing

Authors: Bernard Chazelle

An Optimal Algorithm for Euclidean Shortest Paths in the Plane

JOURNAL ARTICLE published January 1999 in SIAM Journal on Computing

Authors: John Hershberger | Subhash Suri

A Sublinear Space, Polynomial Time Algorithm for Directed s-t Connectivity

JOURNAL ARTICLE published October 1998 in SIAM Journal on Computing

Authors: Greg Barnes | Jonathan F. Buss | Walter L. Ruzzo | Baruch Schieber

Optimal Evaluation of Pairs of Bilinear Forms

JOURNAL ARTICLE published August 1979 in SIAM Journal on Computing

Authors: Joseph JáJá

Padded Lists Revisited

JOURNAL ARTICLE published December 1987 in SIAM Journal on Computing

Authors: Micha Hofri | Alan G. Konheim

An Optimal Lower Bound on the Communication Complexity of Gap-Hamming-Distance

JOURNAL ARTICLE published January 2012 in SIAM Journal on Computing

Authors: Amit Chakrabarti | Oded Regev

Perfect-Information Leader Election with Optimal Resilience

JOURNAL ARTICLE published January 2000 in SIAM Journal on Computing

Authors: Ravi B. Boppana | Babu O. Narayanan

Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model

JOURNAL ARTICLE published January 2002 in SIAM Journal on Computing

Authors: Alexander Russell | Michael Saks | David Zuckerman

Coin-Flipping Games Immune against Linear-Sized Coalitions

JOURNAL ARTICLE published April 1993 in SIAM Journal on Computing

Authors: Noga Alon | Moni Naor

Partial-Match Retrieval Algorithms

JOURNAL ARTICLE published March 1976 in SIAM Journal on Computing

Authors: Ronald L. Rivest

A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability

JOURNAL ARTICLE published January 2019 in SIAM Journal on Computing

Research funded by Engineering and Physical Sciences Research Council (EP/N004221/1)

Authors: Heng Guo | Mark Jerrum

Solving Undirected Graph Problems on VLSI

JOURNAL ARTICLE published August 1985 in SIAM Journal on Computing

Authors: Susanne E. Hambrusch | Janos Simon

Work-Preserving Speed-Up of Parallel Matrix Computations

JOURNAL ARTICLE published August 1995 in SIAM Journal on Computing

Authors: Victor Y. Pan | Franco P. Preparata

Computing $k$-Atomicity in Polynomial Time

JOURNAL ARTICLE published January 2018 in SIAM Journal on Computing

Authors: Wojciech Golab | Xiaozhou Steve | Alejandro López-Ortiz | Naomi Nishimura

An Asymptotically Optimal Algorithm for the Dutch National Flag Problem

JOURNAL ARTICLE published May 1982 in SIAM Journal on Computing

Authors: James R. Bitner

Nonpreemptive LP-Scheduling on Homogeneous Multiprocessor Systems

JOURNAL ARTICLE published February 1981 in SIAM Journal on Computing

Authors: Manfred Kunde

Metric Embeddings with Relaxed Guarantees

JOURNAL ARTICLE published January 2009 in SIAM Journal on Computing

Authors: T.-H. Hubert Chan | Kedar Dhamdhere | Anupam Gupta | Jon Kleinberg | Aleksandrs Slivkins

Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments

JOURNAL ARTICLE published January 2008 in SIAM Journal on Computing

Authors: Sophie Laplante | Frédéric Magniez

Nearly Optimal NP-Hardness of Unique Coverage

JOURNAL ARTICLE published January 2017 in SIAM Journal on Computing

Research funded by National Science Foundation (CCF-1115525)

Authors: Venkatesan Guruswami | Euiwoong Lee