The hardness of computing an eigenform (2007)
In this article, we give evidence that computing Fourier coefficients of the Hecke eigenforms for composite indices is no easier than factoring integers. In particular, we show that the existence of...
Chicago Journal of Theoretical (2003)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
One-dimensional quantum walks with absorbing boundaries (2002)
Bach, Eric, Coppersmith, Susan, Goldschen, Marcel Paz, Joynt, Robert, Watrous, John
In this paper we analyze the behavior of quantum random walks. In particular we present several new results for the absorption probabilities in systems with both one and two absorbing walls for the...
One-Dimensional Quantum Walks (2001)
Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
We define and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard...
Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, ...
The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k...
Random bisection and evolutionary walks (2001)
As models for molecular evolution, immune response, and local search algorithms, various authors have used a stochastic process called the evolutionary walk, which goes as follows. Assign a random...
One-Dimensional Quantum Walks (2001)
Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous
We dene and analyze quantum computational variants of random walks on one-dimensional lattices. In particular, we analyze a quantum analog of the symmetric random walk, which we call the Hadamard...
Quantum Random Walks and the Analysis of Discrete Quantum Processes (2000)
Andris Ambainis, Eric Bach, John Watrous
We dene and analyze quantum computational variants of random walks on one-dimensional lattices. Several striking dierences between the quantum and classical cases are observed. In our analyses we...
E. Bach, J. Boyar, L. Epstein, L. M. Favrholdt, T. Jiang, ...
The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k...
Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, ...
The unit price seat reservation problem is investigated. The seat reservation problem is the problem of assigning seat numbers on-line to requests for reservations in a train traveling through k...
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem (2000)
Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, Guo-hui Lin
In a recent paper [J. Boyar and K.S. Larsen, The seat reservation problem, Algorithmica, 25(1999), 403--417], the seat reservation problem was investigated. It was shown that for the unit price...
Factoring Polynomials Using Fewer Random Bits (1999)
. Let F be a field of q = p n elements, where p is prime. We present two new probabilistic algorithms for factoring polynomials in F [X ] that make particularly efficient use of random bits. They are...
Asymptotic Semismoothness Probabilities (1999)
We call an integer semismooth with respect to y and z if each of its prime factors is y, and all but one are z. Such numbers are useful in various factoring algorithms, including the quadratic sieve....
Threshold Data Structures and Coding Theory (1998)
Data structures for combinatorial objects are traditionally designed to handle objects up to a certain size. We introduce the idea of threshold data structures: representations that allow a richer...
Comments On Search Procedures For Primitive Roots (1997)
. Let p be an odd prime. Assuming the Extended RiemannHypothesis, we show how to construct O((logp) 4 (log log p) Gamma3 ) residues modulo p, one of which must be a primitive root, in deterministic...
The Accommodating Ratio for the Seat Reservation Problem (1997)
Eric Bach, Joan Boyar, Kim S. Larsen
We investigate the problem of giving seat reservations on-line. We assume that a train travels from a start station to an end station, stopping at k stations, including the first and last. Passengers...
Factoring Polynomials Using Fewer Random Bits (1996)
. Let F be a field of q = p n elements, where p is prime. We present two new probabilistic algorithms for factoring polynomials in F [X ] that make particularly efficient use of random bits. They are...
Results And Estimates On Pseudopowers (1995)
Eric Bach, Richard Lukes, Jeffrey Shallit
. Let n be a positive integer. We say n looks like a power of 2 modulo a prime p if there exists an integer ep 0 such that n j 2 ep (mod p). First, we provide a simple proof of the fact that a...
Results And Estimates On Pseudopowers (1995)
Eric Bach, Richard Lukes, Jeffrey Shallit
. Let n be a positive integer. We say n looks like a power of 2 modulo a prime p if there exists an integer ep 0 such that n j 2 ep (mod p). First, we provide a simple proof of the fact that a...
Results And Estimates On Pseudopowers (1995)
Eric Bach, Richard Lukes, Jeffrey Shallit
. Let n be a positive integer. We say n looks like a power of 2 modulo a prime p if there exists an integer ep 0 such that n j 2 ep (mod p). First, we provide a simple proof of the fact that a...
Estimating Mean Completion Times of a Fork-Join Barrier Synchronization (1994)
Eric Bach, Rajesh Mansharamani, John Strikwerda
. In simulation studies of parallel processors, it is useful to consider the following abstraction of a parallel program. A job is partitioned into n processes, whose running times are independent...
Realistic Analysis of Parallel Dynamic Programming Algorithms (1992)
Gary Lewandowski, Anne Condon, Eric Bach
We examine a very simple asynchronous model of parallel computation that assumes the time to compute a task is random, following some probability distribution. The goal of this model is to capture...