February 19, 2001
[1] Chrobak, Gasieniec and Rytter, Fast broadcasting and
gossiping in radio networks, FOCS 2000
www.csc.liv.ac.uk/~leszek/pub.html
[2] Susanne Albers, Better bounds for online scheduling, SICOMP
29 (1999), 459-473.
http://ls2-www.cs.uni-dortmund.de/~albers/#publications
[3] Steven S. Seiden, Online randomized multiprocessor scheduling,
Algorithmica 28(2000), 173-216. hardcopies handed out in class.
[4] Bartal, Fiat, Karloff and Vohra, New algorithms for
an ancient scheduling problem, JCSS 51(1995), 359-366.
www.icsi.berkeley.edu/~yairb/
[5] Jiri Sgall, A lower bound for randomized
on-line multiprocessor scheduling, Information Processing
Letters 63 (1997), 51-55.
www.math.cas.cz/~sgall/papers.html#online
February 26, 2001
[6] A. Ambainis, Communication complexity
in a 3-computer model, Algorithmica 16(1996), 298-301.
copies sent to the class by e-mail.
[7] I. Newman and M. Szegedy, Public vs private coin
flips in one round communication games, 1996 STOC
http://cs.haifa.ac.il/ILAN/online-papers.html
[8] L. Babai and P.G. Kimmel, Randomized
simultaneous messages, Proc. 12th IEEE Symp. on
Computational Complexity, 1997, 239-246.
Download from the tech report section in
http://www.cs.uchicago.edu/people/person.php?login=laci
[9] P. Pudlak, V. Roedl and J. Sgall, Boolean circuits,
tensor ranks, and communication complexity, SICOMP 26(1997),
605-633.
http://www.math.cas.cz/~sgall/papers.html#complexity
[10] N. Nisan and A. Wigderson, Rounds in communication
complexity revisited, Proc. of 1991 STOC, 419-429.
http://www.cs.huji.ac.il/~avi/papers.html
March 5, 2001
[11] Buhrman, Cleve, Watrous, and de Wolf Quantum
fingerprinting, quant-ph/0102001, February 2001
http://xxx.lanl.gov/list/quant-ph/0102
[12] H. Klauck , Quantum communication complexity
quant-ph/0005032, May 2000
http://xxx.lanl.gov/list/quant-ph/0005
[13] Ashwin Nayak Optimal lower bounds for quantum
automata and random access codes,
quant-ph/9904093, September 1999
http://xxx.lanl.gov/list/quant-ph/9904
[14] A. Nayak, A. Ta-Shma, and D. Zuckerman,
Interaction in qunatum communication complexity,
quant-ph/0005106, May 2000
http://xxx.lanl.gov/list/quant-ph/0005
March 26, 2001
[15] H. Buhrman, C. Durr, M. Heiligman, P. Hoyer,
F. Magniez, M. Santha, and R. de Wolf,
Quantum algorithms for Element Distinctness,
quant-ph/0007016, July 2000
http://xxx.lanl.gov/abs/quant-ph/0007016
[16] L. K. Grover,
A Fast Quantum Mechanical Algorithm for Database Search,
Proc. of 1996 STOC, 212-219.
http://www1.bell-labs.com/user/lkgrover/
[17] P. Hoyer, J. Neerbek, and Y. Shi,
Quantum bounds for ordered searching and sorting,
quant-ph/0102078, February 2001
http://xxx.lanl.gov/abs/quant-ph/0102078
