| |
|
|
| |
| |
|
Date Reviewed |
|
| |
1 - 10 of 19
reviews
|
|
|
 |
|
|
|
|
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 |
|
|
|
|
|
|
Exact learning algorithms, betting games, and circuit lower bounds
Harkins R., Hitchcock J. ACM Transactions on Computation Theory 5(4): 1-11, 2013. Type: Article
It is natural to expect that the more complex a concept is, the harder it is to learn. This paper improves this type of correlation for concepts that are represented by a class of circuits
|
Feb 19 2014 |
|
|
|
|
|
|
Computability and complexity theory (2nd ed.)
Homer S., Selman A., Springer Publishing Company, Incorporated, New York, NY, 2011. 314 pp. Type: Book (978-1-461406-81-5)
Every computer scientist should know the basic tenets of computability theory and computational complexity theory--this is why introductory courses on these two fields are quite standard. Consequently, there are several textbo...
|
Apr 27 2012 |
|
|
|
|
|
|
Lattice basis reduction: an introduction to the LLL algorithm and its applications
Bremner M., CRC Press, Inc., Boca Raton, FL, 2011. 332 pp. Type: Book (978-1-439807-02-6)
This is an introductory text on lattice algorithms and their applications. A lattice consists of all vectors that can be expressed as an integer combination of a given fixed set of vectors in Rn (the vecto...
|
Mar 5 2012 |
|
|
|
|
|
|
Primality testing in polynomial time: from randomized algorithms to "Primes Is in P"
Dietzfelbinger M., Springer-Verlag, 2004. Type: Book (9783540403449)
Agrawal, Kayal, and Saxena announced, in 2002, a polynomial-time algorithm (now known as the AKS algorithm) for primality checking, namely, for determining whether a given arbitrary integer is prime or not. This represented the resolut...
|
Oct 19 2004 |
|
|
|
|
|
|
Guide to elliptic curve cryptography
Hankerson D., Menezes A., Vanstone S., Springer-Verlag New York, Inc., Secaucus, NJ, 2003. 332 pp. Type: Book (9780387952734)
Elliptic curves have become a common term in cryptography. They can be used to design entire cryptographic systems, or to implement just specific steps in certain cryptographic protocols. The basic scheme is to let an elliptic curve pr...
|
Jul 8 2004 |
|
|
|
|
|
|
The complexity of propositional linear temporal logics in simple cases
Demri S., Schnoebelen P. Information and Computation 174(1): 84-103, 2002. Type: Article
Propositional linear temporal logic (PLTL) is the basic logical tool that is utilized for the specification and verification of reactive systems. The main syntactic feature of PLTL is that it uses the temporal operators X
|
Jan 8 2003 |
|
|
|
|
|
|
Working with ARMs: complexity results on atomic representations of herbrand models
Gottlob G., Pichler R. Information and Computation 165(2): 183-207, 2001. Type: Article
A finite set of (not necessarily ground) atoms over a given Herbrand universe can represent a possibly infinite Herbrand interpretation. Such a set is called an atomic representation of a Herbrand model (ARM). This paper investigates t...
|
Jun 4 2002 |
|
|
|
|
|
|
Distributional word problem for groups
Wang J. SIAM Journal on Computing 28(4): 1264-1283, 1999. Type: Article
The property of a problem of being NP-complete means only that there are some instances of the problem that are hard to solve (unless, of course, P = N P ). It leaves open the possibility that such instances are unco...
|
Jul 1 2000 |
|
|
|
|
|
|
LOGSPACE and PTIME characterized by programming languages
Jones N. (ed) Theoretical Computer Science 228(1-2): 151-174, 1999. Type: Article
This paper establishes purely syntactical characterizations of the complexity classes PTIME and LOGSPACE. An imperative language is considered that consists basically of the assignment, if-then-else, while, head, and tail...
|
Feb 1 2000 |
|
|
|
|
|
| |
|
|
| |
|
|
