loading...
  • F
  • FOCS
  • 2000
  • 41st Annual Symposium on Foundations of Computer Science
Advanced Search 
41st Annual Symposium on Foundations of Computer Science
Redondo Beach, California
November 12-November 14
ISBN: 0-7695-0850-2
Table of Contents
Session 1, Chair: David Zuckerman
O. Reingold, AT&T Labs.-Res., Florham Park, NJ, USA
S. Vadhan, AT&T Labs.-Res., Florham Park, NJ, USA
A. Wigderson, AT&T Labs.-Res., Florham Park, NJ, USA
pp. 3
N. Alon, Dept. of Math., Tel Aviv Univ., Israel
M. Capalbo, Dept. of Math., Tel Aviv Univ., Israel
Y. Kohayakawa, Dept. of Math., Tel Aviv Univ., Israel
V. Rodl, Dept. of Math., Tel Aviv Univ., Israel
A. Rucinski, Dept. of Math., Tel Aviv Univ., Israel
E. Szemeredi, Dept. of Math., Tel Aviv Univ., Israel
pp. 14
O. Reingold, AT&T Labs.-Res., Florham Park, NJ, USA
R. Shaltiel, AT&T Labs.-Res., Florham Park, NJ, USA
A. Wigderson, AT&T Labs.-Res., Florham Park, NJ, USA
pp. 22
L. Trevisan, Dept. of Comput. Sci., Columbia Univ., New York, NY, USA
S. Vadhan, Dept. of Comput. Sci., Columbia Univ., New York, NY, USA
pp. 32
M. Alekhnovich, Moscow State Univ., Russia
E. Ben-Sasson, Moscow State Univ., Russia
A.A. Razborov, Moscow State Univ., Russia
A. Wigderson, Moscow State Univ., Russia
pp. 43
Session 2, Chair: David Williamson
R. Kumar, IBM Almaden Res. Center, San Jose, CA, USA
P. Raghavan, IBM Almaden Res. Center, San Jose, CA, USA
S. Rajagopalan, IBM Almaden Res. Center, San Jose, CA, USA
D. Sivakumar, IBM Almaden Res. Center, San Jose, CA, USA
A. Tomkins, IBM Almaden Res. Center, San Jose, CA, USA
E. Upfal, IBM Almaden Res. Center, San Jose, CA, USA
pp. 57
R. Karp, Inst. of Int. Comput. Sci., California Univ., Berkeley, CA, USA
E. Koutsoupias, Inst. of Int. Comput. Sci., California Univ., Berkeley, CA, USA
C. Papadimitriou, Inst. of Int. Comput. Sci., California Univ., Berkeley, CA, USA
S. Shenker, Inst. of Int. Comput. Sci., California Univ., Berkeley, CA, USA
pp. 66
A. Kumar, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
J. Kleinberg, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
pp. 75
C.H. Papadimitriou, Dept. of Comput. Sci., California Univ., Berkeley, CA, USA
M. Yannakakis, Dept. of Comput. Sci., California Univ., Berkeley, CA, USA
pp. 86
T. Roughgarden, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
E. Tardos, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
pp. 93
Session 3, Chair: Sanjeev Arora
U. Feige, Dept. of Comput. Sci. & Appl. Math., Weizmann Inst. of Sci., Rehovot, Israel
R. Krauthgamer, Dept. of Comput. Sci. & Appl. Math., Weizmann Inst. of Sci., Rehovot, Israel
pp. 105
Session 4, Chair: Michael Sipser
V. Guruswami, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
J. Hastad, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
M. Sudan, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
pp. 149
V. Guruswami, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
A. Sahai, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
M. Sudan, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
pp. 159
P. Beame, Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
M. Saks, Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
Xiaodong Sun, Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
E. Vee, Dept. of Comput. Sci. & Eng., Washington Univ., Seattle, WA, USA
pp. 169
J. Toran, Abteilung Theor. Inf., Ulm Univ., Germany
pp. 180
Session 5, Chair: R. Ravi
S. Alstrup, Dept. of IT, Copenhagen Univ., Denmark
G. Stolting Brodal, Dept. of IT, Copenhagen Univ., Denmark
T. Rauhe, Dept. of IT, Copenhagen Univ., Denmark
pp. 198
S. Arya, Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Kowloon, China
T. Malamatos, Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Kowloon, China
D.M. Mount, Dept. of Comput. Sci., Hong Kong Univ. of Sci. & Technol., Kowloon, China
pp. 208
T.M. Chan, Dept. of Comput. Sci., Waterloo Univ., Ont., Canada
pp. 219
Session 6, Chair: Avrim Blum
J. Kleinberg, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
pp. 231
N. Alon, Dept. of Math., Tel Aviv Univ., Israel
S. Dar, Dept. of Math., Tel Aviv Univ., Israel
M. Parnas, Dept. of Math., Tel Aviv Univ., Israel
D. Ron, Dept. of Math., Tel Aviv Univ., Israel
pp. 240
T. Batu, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
L. Fortnow, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
R. Rubinfeld, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
W.D. Smith, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
P. White, Dept. of Comput. Sci., Cornell Univ., Ithaca, NY, USA
pp. 259
P. Auer, Inst. for Theor. Comput. Sci., Graz Univ. of Technol., Austria
pp. 270
Session 7, Chair: Joe Kilian
C. Dwork, Compaq Syst. Res. Centre, Palo Alto, CA, USA
M. Naor, Compaq Syst. Res. Centre, Palo Alto, CA, USA
pp. 283
R. Gennaro, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
L. Trevisan, IBM Thomas J. Watson Res. Center, Yorktown Heights, NY, USA
pp. 305
J.A. Garay, Lucent Technol. Bell Labs., Murray Hill, NJ, USA
P. MacKenzie, Lucent Technol. Bell Labs., Murray Hill, NJ, USA
pp. 314
Y. Gertner, Pennsylvania Univ., Philadelphia, PA, USA
S. Kannan, Pennsylvania Univ., Philadelphia, PA, USA
T. Malkin, Pennsylvania Univ., Philadelphia, PA, USA
O. Reingold, Pennsylvania Univ., Philadelphia, PA, USA
M. Viswanathan, Pennsylvania Univ., Philadelphia, PA, USA
pp. 325
Session 8, Chair: Leonard Schulman
R.R. Mettu, Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
C.G. Plaxton, Dept. of Comput. Sci., Texas Univ., Austin, TX, USA
pp. 339
R. Ostrovsky, Telcordia Technol., Morristown, NJ, USA
Y. Rabani, Telcordia Technol., Morristown, NJ, USA
pp. 349
S. Guha, Dept. of Comput. Sci., Stanford Univ., CA, USA
N. Mishra, Dept. of Comput. Sci., Stanford Univ., CA, USA
R. Motwani, Dept. of Comput. Sci., Stanford Univ., CA, USA
L. O'Callaghan, Dept. of Comput. Sci., Stanford Univ., CA, USA
pp. 359
R. Kannan, Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
S. Vempala, Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
A. Veta, Dept. of Comput. Sci., Yale Univ., New Haven, CT, USA
pp. 367
Session 9, Chair: Leonard Schulman
C. Demetrescu, Dipartimento di Inf. e Sistemistica, Rome Univ., Italy
G.F. Italiano, Dipartimento di Inf. e Sistemistica, Rome Univ., Italy
pp. 381
P. Ferragina, Dipt. di Inf., Pisa Univ., Italy
G. Manzini, Dipt. di Inf., Pisa Univ., Italy
pp. 390
M.A. Bender, Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
E.D. Demaine, Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
M. Farach-Colton, Dept. of Comput. Sci., State Univ. of New York, Stony Brook, NY, USA
pp. 399
H.N. Gabow, Dept. of Comput. Sci., Colorado Univ., Boulder, CO, USA
pp. 410
Session 10, Chair: Mario Szegedy
R. Connelly, Dept. of Math., Cornell Univ., Ithaca, NY, USA
E.D. Demaine, Dept. of Math., Cornell Univ., Ithaca, NY, USA
G. Rote, Dept. of Math., Cornell Univ., Ithaca, NY, USA
pp. 432
H. Edelsbrunner, Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
D. Letscher, Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
A. Zomorodian, Dept. of Comput. Sci., Duke Univ., Durham, NC, USA
pp. 454
Session 11, Chair: Leslie Goldberg
J. Kahn, Dept. of Math., Rutgers Univ., New Brunswick, NJ, USA
J.H. Kim, Dept. of Math., Rutgers Univ., New Brunswick, NJ, USA
L. Lovasz, Dept. of Math., Rutgers Univ., New Brunswick, NJ, USA
V.H. Vu, Dept. of Math., Rutgers Univ., New Brunswick, NJ, USA
pp. 467
I. Pak, Dept. of Math., Yale Univ., New Haven, CT, USA
pp. 476
R.A. Martin, Sch. of Math., Georgia Inst. of Technol., Atlanta, GA, USA
D. Randall, Sch. of Math., Georgia Inst. of Technol., Atlanta, GA, USA
pp. 492
J.A. Fill, Dept. of Math. Sci., Johns Hopkins Univ., MD, USA
M. Huber, Dept. of Math. Sci., Johns Hopkins Univ., MD, USA
pp. 503
Session 12, Chair: Umesh Vazirani
L. Hales, Group in Logic & the Methodology of Sci., California Univ., Berkeley, CA, USA
S. Hallgren, Group in Logic & the Methodology of Sci., California Univ., Berkeley, CA, USA
pp. 515
A. Ambainis, California Univ., Berkeley, CA, USA
M. Mosca, California Univ., Berkeley, CA, USA
A. Tapp, California Univ., Berkeley, CA, USA
R. de Wolf, California Univ., Berkeley, CA, USA
pp. 547
J. Radhakrishnan, Sch. of Technol. & Comput. Sci., Tata Inst. of Fundamental Res., Mumbai, India
P. Sen, Sch. of Technol. & Comput. Sci., Tata Inst. of Fundamental Res., Mumbai, India
S. Venkatesh, Sch. of Technol. & Comput. Sci., Tata Inst. of Fundamental Res., Mumbai, India
pp. 554
Session 13, Chair: Leslie Goldberg
R. Karp, California Univ., Berkeley, CA, USA
C. Schindelhauer, California Univ., Berkeley, CA, USA
S. Shenker, California Univ., Berkeley, CA, USA
B. Vocking, California Univ., Berkeley, CA, USA
pp. 565
M. Chrobak, Dept. of Comput. Sci., California Univ., Riverside, CA, USA
L. Gasieniec, Dept. of Comput. Sci., California Univ., Riverside, CA, USA
W. Rytter, Dept. of Comput. Sci., California Univ., Riverside, CA, USA
pp. 575
D. Achioptas, Microsoft Res., Redmond, WA, USA
G.B. Sorkin, Microsoft Res., Redmond, WA, USA
pp. 590
Session 14, Chair: David Williamson
S. Guha, Dept. of Comput. Sci., Stanford Univ., CA, USA
A. Meyerson, Dept. of Comput. Sci., Stanford Univ., CA, USA
K. Munagala, Dept. of Comput. Sci., Stanford Univ., CA, USA
pp. 603
D.R. Karget, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
M. Minkoff, Lab. for Comput. Sci., MIT, Cambridge, MA, USA
pp. 613
A. Meyerson, Dept. of Comput. Sci., Stanford Univ., CA, USA
K. Munagala, Dept. of Comput. Sci., Stanford Univ., CA, USA
S. Plotkin, Dept. of Comput. Sci., Stanford Univ., CA, USA
pp. 624
M. Charikar, Dept. of Comput. Sci., Stanford Univ., CA, USA
V. Guruswami, Dept. of Comput. Sci., Stanford Univ., CA, USA
R. Kumar, Dept. of Comput. Sci., Stanford Univ., CA, USA
S. Rajagopalan, Dept. of Comput. Sci., Stanford Univ., CA, USA
A. Sahai, Dept. of Comput. Sci., Stanford Univ., CA, USA
pp. 631
Session 15, Chair: Michael Sipser
M. Maidi, Siemens Corp. Technol., Munchen, Germany
pp. 643
M. Herlihy, Dept. of Comput. Sci., Brown Univ., Providence, RI, USA
E. Ruppert, Dept. of Comput. Sci., Brown Univ., Providence, RI, USA
pp. 653
W. Eberly, Dept. of Comput. Sci., Calgary Univ., Alta., Canada
M. Giesbrecht, Dept. of Comput. Sci., Calgary Univ., Alta., Canada
G. Villard, Dept. of Comput. Sci., Calgary Univ., Alta., Canada
pp. 675
Usage of this product signifies your acceptance of the Terms of Use.