| |
1-10 of 10 reviews |
Date Reviewed | |
| |
Short lists for shortest descriptions in short time
Teutsch J. Computational Complexity 23(4): 565-583, 2014. Type: Article
Compressing a string to its shortest description (in the sense of Kolmogorov complexity) cannot be done effectively. This paper belongs to a recent research line that investigates the list approximability of the problem, namely whether...
|
Mar 3 2015 |
|
| |
Balancing syntactically multilinear arithmetic circuits
Raz R., Yehudayoff A. Computational Complexity 17(4): 515-535, 2008. Type: Article
Most computer designs only support arithmetic operations in hardware (and, thus, are fast). Among these operations, addition and multiplication are much faster than division. As a result, most programs compute, in effect, the value of ...
|
May 15 2009 |
|
| |
Polynomial multiplication over finite fields: from quadratic to straight-line complexity
Bshouty N., Kaminski M. Computational Complexity 15(3): 252-262, 2006. Type: Article
Let &lgr;(n) be the number of multiplications/divisions required to compute the coefficients of the product of a polynomial of degree n and a polynomial of degree n-1 ove...
|
Aug 15 2007 |
|
| |
Efficient algorithm for computing the Euler-Poincaré characteristic of a semi-algebraic set defined by few quadratic inequalities
Basu S. Computational Complexity 15(3): 236-251, 2006. Type: Article
In recent years, there has been a strong effort in computational real algebraic geometry to provide algorithms (and corresponding complexity estimates) for determining the geometric and topological properties of semialgebraic sets, nam...
|
Jul 31 2007 |
|
| |
Quantum computation of zeta functions of curves
Kedlaya K. Computational Complexity 15(1): 1-19, 2006. Type: Article
Quantum computation presupposes that an extremely reliable probabilistic result found “logarithmically fast” by a quantum computer is in practice preferable to an accurate (but exponential time) result. The ...
|
Nov 22 2006 |
|
| |
Circuits on cylinders
Hansen K., Miltersen P., Vinay V. Computational Complexity 15(1): 62-81, 2006. Type: Article
The path-breaking results of Furst, Saxe, and Sipser and of Ajtai in the early 1980s established that polynomial-sized constant depth circuits AC0 cannot compute PARITY. Since then, the small circuit classes AC0, ...
|
Nov 6 2006 |
|
| |
On interactive proofs with a laconic prover
Goldreich O., Vadhan S., Wigderson A. Computational Complexity 11(1/2): 1-53, 2003. Type: Article
As the authors state, “Interactive proof systems are two-party randomized protocols through which a computationally unbounded prover can convince a probabilistic polynomial-time verifier of the membership of a common input in...
|
Dec 21 2004 |
|
| |
Reducing the complexity of reductions
Agrawal M., Allender E., Impagliazzo R., Pitassi T., Rudich S. Computational Complexity 10(2): 117-138, 2002. Type: Article
The authors investigate separations and collapses in the power of reductions, in terms of their making sets complete for classes, and the stronger results implicit in certain types of completeness....
|
Nov 22 2002 |
|
| |
A comparison of group and individual performance among subject experts and untrained workers at the document retrieval task
Wilbur W. Computational Complexity 49(6): 517-529, 1998. Type: Article
In this paper, queries are by example: A query is a relevant document, and the users are looking for documents as similar to that one as possible. The information retrieval system ranks the documents using the vector space model, that ...
|
Nov 1 1999 |
|
| |
User satisfaction with information seeking on the Internet
Bruce H. Computational Complexity 49(6): 541-556, 1998. Type: Article
In 1996 and 1997 (ancient history in Internet terms), Bruce studied how satisfied Australian academics were by the results of their searches for information on the Internet. The bottom line is that they generally were satisfied....
|
Sep 1 1999 |
|
| |
|
|
| |
|
|
|
|
