The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study Through Datalog and Group Theory
- Tomás Feder
- Moshe Y. Vardi
- 1998
- SIAM Journal on Computing
Publications
This is our catalog of publications authored by IBM researchers, in collaboration with the global research community. It’s an ever-growing body of work that shows why IBM is one of the most important contributors to modern computing.
Date
Featured collections
Popular topics
123 results at SIAM Journal on Computing
A sublinear time distributed algorithm for minimum-weight spanning trees
- Juan A. Garay
- Shay Kutten
- et al.
- 1998
- SIAM Journal on Computing
Fully polynomial byzantine agreement for n > 3t processors in t + 1 rounds
- Juan A. Garay
- Yoram Moses
- 1998
- SIAM Journal on Computing
Performing work efficiently in the presence of faults
- Cynthia Dwork
- 1998
- SIAM Journal on Computing
Bounding the power of preemption in randomized scheduling
- Ran Canetti
- Sandy Irani
- 1998
- SIAM Journal on Computing
Lower bounds for randomized mutual exclusion
- Eyal Kushilevitz
- Yishay Mansour
- et al.
- 1998
- SIAM Journal on Computing
On syntactic versus computational views of approximability
- Sanjeev Khanna
- Rajeev Motwani
- et al.
- 1998
- SIAM Journal on Computing
Efficient Self-embedding Of Butterfly Networks With Random Faults
- Hisao Tamaki
- 1998
- SIAM Journal on Computing
Strengths and weaknesses of quantum computing
- Charles H. Bennett
- Ethan Bernstein
- et al.
- 1997
- SIAM Journal on Computing
The robot localization problem
- Leonidas J. Guibas
- Rajeev Motwani
- et al.
- 1997
- SIAM Journal on Computing