| |
1-10 of 323 reviews |
Date Reviewed | |
| |
Playing games with approximation algorithms
Kakade S., Kalai A., Ligett K. SIAM Journal on Computing 39(3): 1088-1106, 2009. Type: Article
Suppose a delivery truck visits the same customers every day, but traffic conditions are unknown and vary. What is the best route for the truck to take? This is one (briefly mentioned) example of the kind of problem addressed by this p...
|
Jun 16 2010 |
|
| |
Optimal power-down strategies
Augustine J., Irani S., Swamy C. SIAM Journal on Computing 37(5): 1499-1516, 2008. Type: Article
Electronic devices usually offer many functions; most of them, though critical for the correct operation of the device, are hidden from the user. Each function has its own power requirements; all functions are active at the same time, ...
|
Oct 9 2008 |
|
| |
Identity-based encryption from the Weil pairing
Boneh D., Franklin M. SIAM Journal on Computing 32(3): 586-615, 2003. Type: Article
An identity-based cryptosystem is a public key cryptosystem that allows arbitrary public keys; this paper presents a complete description of one. The encryption and decryption are reminiscent of the Diffie-Hellman and El Gamal systems,...
|
Jun 7 2007 |
|
| |
Reconstructing chromosomal evolution
Wang L., Warnow T. SIAM Journal on Computing 36(1): 99-131, 2006. Type: Article
Wang and Warnow introduce two polynomial time algorithms, EXACT-IEBP and Approx-IEBP, for estimating the actual number of rearrangements that have taken place in the evolutionary history between two chromosomes. They employ inversions,...
|
Apr 4 2007 |
|
| |
Online scheduling of precedence constrained tasks
Huo Y., Leung J. SIAM Journal on Computing 34(3): 743-762, 2005. Type: Article
Scheduling theory has received a lot of attention in the last few years. Basic scheduling theory deals with the problem of scheduling n tasks, with precedence constraints, on m machines. Each task ...
|
Feb 6 2007 |
|
| |
The computational complexity of Tutte invariants for planar graphs
Vertigan D. SIAM Journal on Computing 35(3): 690-712, 2005. Type: Article
The Tutte polynomial for a graph (or matroid) is a two-variable polynomial that summarizes many of the graph’s invariants. The values of these invariants can be obtained by evaluating the Tutte polynomial at an appropriat...
|
Jan 16 2007 |
|
| |
Bounds on the efficiency of generic cryptographic constructions
Gennaro R., Gertner Y., Katz J., Trevisan L. SIAM Journal on Computing 35(1): 217-246, 2005. Type: Article
This paper studies the possibility of improving the efficiency of cryptographic protocols when they are based on general assumptions. The overall result obtained is that the efficiency of many of the known constructions based on genera...
|
Mar 30 2006 |
|
| |
SRT division algorithms as dynamical systems
McCann M., Pippenger N. SIAM Journal on Computing 34(6): 1279-1301, 2005. Type: Article
This paper investigates a family of division algorithms (referred to as Sweeney-Robertson-Tocher (SRT)) as examples of dynamical systems. Although the main result of the paper can be understood without recourse to the dynamical systems...
|
Feb 23 2006 |
|
| |
The difficulty of testing for isomorphism against a graph that is given in advance
Fischer E. SIAM Journal on Computing 34(5): 1147-1158, 2005. Type: Article
Consider graphs G and H. This paper investigates how many queries are required to test the input graph G for the property of being isomorphic to H. A formal de...
|
Feb 10 2006 |
|
| |
Pseudorandom generators in propositional proof complexity
Alekhnovich M., Ben-Sasson E., Razborov A., Wigderson A. SIAM Journal on Computing 34(1): 67-88, 2005. Type: Article
This paper studies the complexity of the inconsistent statement for a system of Boolean functions (S): g1(x1,...,xn)=...
|
Aug 4 2005 |
|
| |
|
|
| |
|
|
|
|
