Tight Bounds for Testing Bipartiteness in General Graphs

JOURNAL ARTICLE published January 2004 in SIAM Journal on Computing

Authors: Tali Kaufman | Michael Krivelevich | Dana Ron

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

Nonindependent Randomized Rounding and an Application to Digital Halftoning

JOURNAL ARTICLE published January 2005 in SIAM Journal on Computing

Authors: Benjamin Doerr

A Correctness Condition for High-Performance Multiprocessors

JOURNAL ARTICLE published December 1998 in SIAM Journal on Computing

Authors: Hagit Attiya | Roy Friedman

Mitotic Classes in Inductive Inference

JOURNAL ARTICLE published January 2008 in SIAM Journal on Computing

Authors: Sanjay Jain | Frank Stephan

Single Machine Job Sequencing with Precedence Constraints

JOURNAL ARTICLE published March 1977 in SIAM Journal on Computing

Authors: Donald L. Adolphson

Sums of Divisors, Perfect Numbers and Factoring

JOURNAL ARTICLE published November 1986 in SIAM Journal on Computing

Authors: Eric Bach | Gary Miller | Jeffrey Shallit

A Simple Unpredictable Pseudo-Random Number Generator

JOURNAL ARTICLE published May 1986 in SIAM Journal on Computing

Authors: L. Blum | M. Blum | M. Shub

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

JOURNAL ARTICLE published January 2010 in SIAM Journal on Computing

Authors: A. Ambainis | A. M. Childs | B. W. Reichardt | R. Špalek | S. Zhang

Completion of a Set of Rules Modulo a Set of Equations

JOURNAL ARTICLE published November 1986 in SIAM Journal on Computing

Authors: Jean-Pierre Jouannaud | Hélène Kirchner

Matrix Factorization over $GF(2)$ and Trace-Orthogonal Bases of $GF(2^n )$

JOURNAL ARTICLE published June 1975 in SIAM Journal on Computing

Authors: Abraham Lempel

Data Types as Lattices

JOURNAL ARTICLE published September 1976 in SIAM Journal on Computing

Authors: Dana Scott

Preface

JOURNAL ARTICLE published March 1972 in SIAM Journal on Computing

Authors: Philip M. Lewis, II