# Search results for: Eric Bach

Journal of Symbolic Computation > 2018 > 85 > C > 55-71

Lecture Notes in Computer Science > Computing and Combinatorics > Randomized and Average-Case Algorithms > 473-482

*cannot*be completely derandomized by any specified set of rational approximations to algebraic numbers up to a polynomial number of bits. The proof is a direct application of Dirichlet’s box principle. We also give some number theoretic estimates for the likelihood of a multiplicatively...

*Algorithmica*, 25(1999), 403–417], the

*seat reservation problem*was investigated. It was shown that for the

*unit price problem*, where all tickets have the same price, all “fair” algorithms are at least 1/2-accommodating, while no fair algorithm is more than (4/5+

*O*(1/

*k*))-accommodating, where

*k*is the number of stations the train...

Lecture Notes in Computer Science > Theory and Applications of Models of Computation > Contributed Papers > 632-645

Lecture Notes in Computer Science > Computing and Combinatorics > Data Structure and Sampling Theory > 489-499

Linear Algebra and Its Applications > 2013 > 439 > 5 > 1312-1320

_{n}(q).

Journal of Complexity > 2009 > 25 > 6 > 511-529

Information Processing Letters > 2007 > 101 > 2 > 86-92

Japan Journal of Industrial and Applied Mathematics > 2007 > 24 > 3 > 229-239

*n*is congruent if there is a triangle with rational sides whose area is

*n*. In the 1980s Tunnell gave an algorithm to test congruence which relied on counting integral points on the ellipsoids 2

*x*

^{2}+

*y*

^{2}+ 8

*z*

^{2}=

*n*and 2

*x*

^{2}+

*y*

^{2}+ 32

*z*

^{2}=

*n*. The correctness of this algorithm is conditional on the conjecture of Birch and Swinnerton-Dyer. The known methods for testing Tunnell’s criterion use

*O*(

*n*...

Journal of Computer and System Sciences > 2004 > 69 > 4 > 562-592

Theoretical Computer Science > 2003 > 296 > 1 > 15-25

Journal of Scheduling > 2003 > 6 > 2 > 131-147

*k*stations. We are considering the version where all tickets have the same price and where requests are treated fairly, that is, a request which can be fulfilled must be granted. For fair deterministic algorithms,...

Finite Fields and Their Applications > 2001 > 7 > 1 > 5-28

_{k}(p) is built up from small prime factors; here Φ

_{k}denotes the kth cyclotomic polynomial, and p is the characteristic of the field. In the case k=1, when Φ

_{k}(p)=p−1, such an algorithm was known, and its analysis required the generalized...

Journal of Computer and System Sciences > 1998 > 57 > 2 > 172-186

Statistics and Probability Letters > 1997 > 36 > 1 > 1-7

_{r}(n

^{2}) - P

_{r}(x

^{2}), where P

_{r}is a degree r polynomial, and evaluate P

_{r}for r = 1, ,6. Measured in...

Information Processing Letters > 1997 > 62 > 3 > 145-152

^{3}

^{+}

^{o}

^{(}

^{1}

^{)}bit operations. The factor implied by the symbol o(1) depends on the cost of the underlying arithmetic, but for practical purposes can be taken as log t. As a by-product of this work, we estimate the complexity of computing Bernoulli numbers...

Performance Evaluation > 1996 > 26 > 2 > 145-154

_{1}X

_{n}. As a measure of performance we consider the normalized job completion timeS = max{X

_{i}}Σi=1nX

_{i}. We consider a simple approximation...