Publications

4 results at FOCS 1989

On the power of 2-way probabilistic finite state automata
- - Cynthia Dwork
  - Larry Stockmeyer
- 1989
- FOCS 1989
Datalog vs. first-order logic
- - Miklos Ajtai
  - Yuri Gurevich
- 1989
- FOCS 1989
Constant depth circuits, Fourier transform, and learnability
- - Nathan Linial
  - Yishay Mansour
  - et al.
- 1989
- FOCS 1989
Graph products and chromatic numbers
- - Nathan Linial
  - Umesh Vazirani
- 1989
- FOCS 1989

On the power of 2-way probabilistic finite state automata