%%% -*-BibTeX-*-
%%% ====================================================================
%%% BibTeX-file{
%%% author = "Nelson H. F. Beebe",
%%% version = "2.01",
%%% date = "23 March 2007",
%%% time = "06:39:15 MDT",
%%% filename = "focs2000.bib",
%%% address = "University of Utah
%%% Department of Mathematics, 110 LCB
%%% 155 S 1400 E RM 233
%%% Salt Lake City, UT 84112-0090
%%% USA",
%%% telephone = "+1 801 581 5254",
%%% FAX = "+1 801 581 4148",
%%% URL = "http://www.math.utah.edu/~beebe",
%%% checksum = "26079 4373 15564 193657",
%%% email = "beebe at math.utah.edu, beebe at acm.org,
%%% beebe at computer.org (Internet)",
%%% codetable = "ISO/ASCII",
%%% keywords = "bibliography; BibTeX; Foundations of Computer
%%% Science (FOCS)",
%%% license = "public domain",
%%% supported = "yes",
%%% docstring = "This is a COMPLETE bibliography of
%%% publications in the annual IEEE symposia on
%%% the Foundations of Computer Science (CODEN
%%% ASFPDV, ISSN 0272-5428) for the decade
%%% 2000--2009.
%%%
%%% At version 2.01, the year coverage looked like
%%% this:
%%%
%%% 2000 ( 66) 2002 ( 82) 2004 ( 65)
%%% 2001 ( 63) 2003 ( 66)
%%%
%%% InProceedings: 337
%%% Proceedings: 5
%%%
%%% Total entries: 342
%%%
%%% Data for this bibliography has been derived
%%% from the IEEE Xplore database, and online
%%% library catalogs.
%%%
%%% In this bibliography, entries are sorted in
%%% publication order, using `bibsort -bypages'.
%%%
%%% The checksum field above contains a CRC-16
%%% checksum as the first value, followed by the
%%% equivalent of the standard UNIX wc (word
%%% count) utility output of lines, words, and
%%% characters. This is produced by Robert
%%% Solovay's checksum utility.",
%%% }
%%% ====================================================================
@Preamble{
"\ifx \mathbb \undefined \def \mathbb #1{{\bf #1}} \fi"
}
%%% ====================================================================
%%% Acknowledgement abbreviations:
@String{ack-nhfb = "Nelson H. F. Beebe,
University of Utah,
Department of Mathematics, 110 LCB
155 S 1400 E RM 233,
Salt Lake City, UT 84112-0090, USA,
Tel: +1 801 581 5254,
FAX: +1 801 581 4148,
e-mail: \path|beebe@math.utah.edu|,
\path|beebe@acm.org|,
\path|beebe@computer.org| (Internet),
URL: \path|http://www.math.utah.edu/~beebe/|"}
%%% ====================================================================
%%% Publisher abbreviations:
@String{pub-IEEE = "IEEE Computer Society Press"}
@String{pub-IEEE:adr = "1109 Spring Street, Suite 300,
Silver Spring, MD 20910, USA"}
%%% ====================================================================
%%% Bibliography entries:
@InProceedings{Reingold:2000:EWZ,
author = "O. Reingold and S. Vadhan and A. Wigderson",
title = "Entropy waves, the zig-zag graph product, and new
constant-degree expanders and extractors",
crossref = "IEEE:2000:ASF",
pages = "3--13",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:2000:UT,
author = "N. Alon and M. Capalbo and Y. Kohayakawa and V. Rodl
and A. Rucinski and E. Szemeredi",
title = "Universality and tolerance",
crossref = "IEEE:2000:ASF",
pages = "14--21",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Reingold:2000:ERR,
author = "O. Reingold and R. Shaltiel and A. Wigderson",
title = "Extracting randomness via repeated condensing",
crossref = "IEEE:2000:ASF",
pages = "22--31",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Trevisan:2000:ERS,
author = "L. Trevisan and S. Vadhan",
title = "Extracting randomness from samplable distributions",
crossref = "IEEE:2000:ASF",
pages = "32--42",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2000:PGP,
author = "M. Alekhnovich and E. Ben-Sasson and A. A. Razborov
and A. Wigderson",
title = "Pseudorandom generators in propositional proof
complexity",
crossref = "IEEE:2000:ASF",
pages = "43--53",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kumar:2000:SMW,
author = "R. Kumar and P. Raghavan and S. Rajagopalan and D.
Sivakumar and A. Tomkins and E. Upfal",
title = "Stochastic models for the {Web} graph",
crossref = "IEEE:2000:ASF",
pages = "57--65",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Karp:2000:OPC,
author = "R. Karp and E. Koutsoupias and C. Papadimitriou and S.
Shenker",
title = "Optimization problems in congestion control",
crossref = "IEEE:2000:ASF",
pages = "66--74",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kumar:2000:FMR,
author = "A. Kumar and J. Kleinberg",
title = "Fairness measures for resource allocation",
crossref = "IEEE:2000:ASF",
pages = "75--85",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Papadimitriou:2000:ATO,
author = "C. H. Papadimitriou and M. Yannakakis",
title = "On the approximability of trade-offs and optimal
access of {Web} sources",
crossref = "IEEE:2000:ASF",
pages = "86--92",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Roughgarden:2000:HBS,
author = "T. Roughgarden and E. Tardos",
title = "How bad is selfish routing?",
crossref = "IEEE:2000:ASF",
pages = "93--102",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Feige:2000:PAM,
author = "U. Feige and R. Krauthgamer",
title = "A polylogarithmic approximation of the minimum
bisection",
crossref = "IEEE:2000:ASF",
pages = "105--115",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Sviridenko:2000:AAR,
author = "M. Sviridenko and G. J. Woeginger",
title = "Approximability and in-approximability results for
no-wait shop scheduling",
crossref = "IEEE:2000:ASF",
pages = "116--125",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Guha:2000:NGD,
author = "S. Guha",
title = "Nested graph dissection and approximation algorithms",
crossref = "IEEE:2000:ASF",
pages = "126--135",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Skutella:2000:ASS,
author = "M. Skutella",
title = "Approximating the single source unsplittable min-cost
flow problem",
crossref = "IEEE:2000:ASF",
pages = "136--145",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Guruswami:2000:HAH,
author = "V. Guruswami and J. Hastad and M. Sudan",
title = "Hardness of approximate hypergraph coloring",
crossref = "IEEE:2000:ASF",
pages = "149--158",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Guruswami:2000:SDD,
author = "V. Guruswami and A. Sahai and M. Sudan",
title = "``Soft-decision'' decoding of {Chinese} remainder
codes",
crossref = "IEEE:2000:ASF",
pages = "159--168",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Beame:2000:SLT,
author = "P. Beame and M. Saks and Xiaodong Sun and E. Vee",
title = "Super-linear time-space tradeoff lower bounds for
randomized computation",
crossref = "IEEE:2000:ASF",
pages = "169--179",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Toran:2000:HGI,
author = "J. Toran",
title = "On the hardness of graph isomorphism",
crossref = "IEEE:2000:ASF",
pages = "180--186",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Indyk:2000:SDP,
author = "P. Indyk",
title = "Stable distributions, pseudorandom generators,
embeddings and data stream computation",
crossref = "IEEE:2000:ASF",
pages = "189--197",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alstrup:2000:NDS,
author = "S. Alstrup and G. Stolting Brodal and T. Rauhe",
title = "New data structures for orthogonal range searching",
crossref = "IEEE:2000:ASF",
pages = "198--207",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Arya:2000:NOE,
author = "S. Arya and T. Malamatos and D. M. Mount",
title = "Nearly optimal expected-case planar point location",
crossref = "IEEE:2000:ASF",
pages = "208--218",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Chan:2000:LAC,
author = "T. M. Chan",
title = "On levels in arrangements of curves",
crossref = "IEEE:2000:ASF",
pages = "219--227",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kleinberg:2000:DNF,
author = "J. Kleinberg",
title = "Detecting a network failure",
crossref = "IEEE:2000:ASF",
pages = "231--239",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:2000:TC,
author = "N. Alon and S. Dar and M. Parnas and D. Ron",
title = "Testing of clustering",
crossref = "IEEE:2000:ASF",
pages = "240--250",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Newman:2000:TFS,
author = "I. Newman",
title = "Testing of function that have small width branching
programs",
crossref = "IEEE:2000:ASF",
pages = "251--258",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Batu:2000:TDC,
author = "T. Batu and L. Fortnow and R. Rubinfeld and W. D.
Smith and P. White",
title = "Testing that distributions are close",
crossref = "IEEE:2000:ASF",
pages = "259--269",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Auer:2000:UUC,
author = "P. Auer",
title = "Using upper confidence bounds for online learning",
crossref = "IEEE:2000:ASF",
pages = "270--279",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Dwork:2000:ZTA,
author = "C. Dwork and M. Naor",
title = "Zaps and their applications",
crossref = "IEEE:2000:ASF",
pages = "283--293",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Ishai:2000:RPN,
author = "Y. Ishai and E. Kushilevitz",
title = "Randomizing polynomials: {A} new representation with
applications to round-efficient secure computation",
crossref = "IEEE:2000:ASF",
pages = "294--304",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gennaro:2000:LBE,
author = "R. Gennaro and L. Trevisan",
title = "Lower bounds on the efficiency of generic
cryptographic constructions",
crossref = "IEEE:2000:ASF",
pages = "305--313",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Garay:2000:COT,
author = "J. A. Garay and P. MacKenzie",
title = "Concurrent oblivious transfer",
crossref = "IEEE:2000:ASF",
pages = "314--324",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gertner:2000:RBP,
author = "Y. Gertner and S. Kannan and T. Malkin and O. Reingold
and M. Viswanathan",
title = "The relationship between public key encryption and
oblivious transfer",
crossref = "IEEE:2000:ASF",
pages = "325--335",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Mettu:2000:OMP,
author = "R. R. Mettu and C. G. Plaxton",
title = "The online median problem",
crossref = "IEEE:2000:ASF",
pages = "339--348",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Ostrovsky:2000:PTA,
author = "R. Ostrovsky and Y. Rabani",
title = "Polynomial time approximation schemes for geometric
$k$-clustering",
crossref = "IEEE:2000:ASF",
pages = "349--358",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Guha:2000:CDS,
author = "S. Guha and N. Mishra and R. Motwani and L.
O'Callaghan",
title = "Clustering data streams",
crossref = "IEEE:2000:ASF",
pages = "359--366",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kannan:2000:CGB,
author = "R. Kannan and S. Vempala and A. Vetta",
title = "On clusterings --- good, bad and spectral",
crossref = "IEEE:2000:ASF",
pages = "367--377",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Demetrescu:2000:FDT,
author = "C. Demetrescu and G. F. Italiano",
title = "Fully dynamic transitive closure: breaking through the
{$O(n^2)$} barrier",
crossref = "IEEE:2000:ASF",
pages = "381--389",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Ferragina:2000:ODS,
author = "P. Ferragina and G. Manzini",
title = "Opportunistic data structures with applications",
crossref = "IEEE:2000:ASF",
pages = "390--398",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Bender:2000:COT,
author = "M. A. Bender and E. D. Demaine and M. Farach-Colton",
title = "Cache-oblivious $b$-trees",
crossref = "IEEE:2000:ASF",
pages = "399--409",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gabow:2000:UEG,
author = "H. N. Gabow",
title = "Using expander graphs to find vertex connectivity",
crossref = "IEEE:2000:ASF",
pages = "410--420",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Pach:2000:BCU,
author = "J. Pach and G. Tardos",
title = "On the boundary complexity of the union of fat
triangles",
crossref = "IEEE:2000:ASF",
pages = "423--431",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Connelly:2000:SPA,
author = "R. Connelly and E. D. Demaine and G. Rote",
title = "Straightening polygonal arcs and convexifying
polygonal cycles",
crossref = "IEEE:2000:ASF",
pages = "432--442",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Streinu:2000:CAP,
author = "I. Streinu",
title = "A combinatorial approach to planar non-colliding robot
arm motion planning",
crossref = "IEEE:2000:ASF",
pages = "443--453",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Edelsbrunner:2000:TPS,
author = "H. Edelsbrunner and D. Letscher and A. Zomorodian",
title = "Topological persistence and simplification",
crossref = "IEEE:2000:ASF",
pages = "454--463",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kahn:2000:CTB,
author = "J. Kahn and J. H. Kim and L. Lovasz and V. H. Vu",
title = "The cover time, the blanket time, and the {Matthews}
bound",
crossref = "IEEE:2000:ASF",
pages = "467--475",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Pak:2000:PRA,
author = "I. Pak",
title = "The product replacement algorithm is polynomial",
crossref = "IEEE:2000:ASF",
pages = "476--485",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kalai:2000:EAU,
author = "A. Kalai and S. Vempala",
title = "Efficient algorithms for universal portfolios",
crossref = "IEEE:2000:ASF",
pages = "486--491",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Martin:2000:SAS,
author = "R. A. Martin and D. Randall",
title = "Sampling adsorbing staircase walks using a new
{Markov} chain decomposition method",
crossref = "IEEE:2000:ASF",
pages = "492--502",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Fill:2000:RRN,
author = "J. A. Fill and M. Hubert",
title = "The randomness recycler: a new technique for perfect
sampling",
crossref = "IEEE:2000:ASF",
pages = "503--511",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Hales:2000:IQF,
author = "L. Hales and S. Hallgren",
title = "An improved quantum {Fourier} transform algorithm and
applications",
crossref = "IEEE:2000:ASF",
pages = "515--525",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Cleve:2000:FPC,
author = "R. Cleve and J. Watrous",
title = "Fast parallel circuits for the quantum {Fourier}
transform",
crossref = "IEEE:2000:ASF",
pages = "526--536",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Watrous:2000:SQP,
author = "J. Watrous",
title = "Succinct quantum proofs for properties of finite
groups",
crossref = "IEEE:2000:ASF",
pages = "537--546",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Ambainis:2000:PQC,
author = "A. Ambainis and M. Mosca and A. Tapp and R. de Wolf",
title = "Private quantum channels",
crossref = "IEEE:2000:ASF",
pages = "547--553",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Radhakrishnan:2000:QCS,
author = "J. Radhakrishnan and Pranab Sen and S. Venkatesh",
title = "The quantum complexity of set membership",
crossref = "IEEE:2000:ASF",
pages = "554--562",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Karp:2000:RRS,
author = "R. Karp and C. Schindelhauert and S. Shenkert and B.
Vocking",
title = "Randomized rumor spreading",
crossref = "IEEE:2000:ASF",
pages = "565--574",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Chrobak:2000:FBG,
author = "M. Chrobak and L. Gasieniec and W. Rytter",
title = "Fast broadcasting and gossiping in radio networks",
crossref = "IEEE:2000:ASF",
pages = "575--581",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kenyon:2000:LWB,
author = "C. Kenyon and M. Mitzenmacher",
title = "Linear waste of best fit bin packing on skewed
distributions",
crossref = "IEEE:2000:ASF",
pages = "582--589",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Achhoptas:2000:OMA,
author = "D. Achhoptas and G. B. Sorkin",
title = "Optimal myopic algorithms for random $3$-{SAT}",
crossref = "IEEE:2000:ASF",
pages = "590--600",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Guha:2000:HPN,
author = "S. Guha and A. Meyerson and K. Munagala",
title = "Hierarchical placement and network design problems",
crossref = "IEEE:2000:ASF",
pages = "603--612",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Karger:2000:BST,
author = "D. R. Karger and M. Minkoff",
title = "Building {Steiner} trees with incomplete global
knowledge",
crossref = "IEEE:2000:ASF",
pages = "613--623",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Meyerson:2000:CDT,
author = "A. Meyerson and K. Munagala and S. Plotkin",
title = "{COST} {DISTANCE}: two metric network design",
crossref = "IEEE:2000:ASF",
pages = "624--630",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Charikar:2000:CFS,
author = "M. Charikar and V. Guruswami and R. Kumar and S.
Rajagopalan and A. Sahai",
title = "Combinatorial feature selection problems",
crossref = "IEEE:2000:ASF",
pages = "631--640",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Maidl:2000:CFC,
author = "M. Maidl",
title = "The common fragment of {CTL} and {LTL}",
crossref = "IEEE:2000:ASF",
pages = "643--652",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Herlihy:2000:EBT,
author = "M. Herlihy and E. Ruppert",
title = "On the existence of booster types",
crossref = "IEEE:2000:ASF",
pages = "653--663",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gottlob:2000:ESO,
author = "G. Gottlob and P. G. Kolaitis and T. Schwentick",
title = "Existential second-order logic over graphs: charting
the tractability frontier",
crossref = "IEEE:2000:ASF",
pages = "664--674",
year = "2000",
bibdate = "Thu Apr 5 06:14:11 MDT 2001",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2001:ISF,
author = "Anonymous",
title = "{42nd IEEE Symposium on Foundations of Computer
Science}",
crossref = "IEEE:2001:ISF",
pages = "i--viii",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Papadimitriou:2001:GTM,
author = "C. H. Papadimitriou",
title = "Game theory and mathematical economics: a theoretical
computer scientist's introduction",
crossref = "IEEE:2001:ISF",
pages = "4--8",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Indyk:2001:AAL,
author = "P. Indyk",
title = "Algorithmic applications of low-distortion geometric
embeddings",
crossref = "IEEE:2001:ISF",
pages = "10--33",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Sudan:2001:CTT,
author = "M. Sudan",
title = "Coding theory: tutorial \& survey",
crossref = "IEEE:2001:ISF",
pages = "36--53",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Koltun:2001:ATU,
author = "V. Koltun",
title = "Almost tight upper bounds for vertical decompositions
in four dimensions",
crossref = "IEEE:2001:ISF",
pages = "56--65",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Har-Peled:2001:ASF,
author = "S. Har-Peled and K. R. Varadarajan",
title = "Approximate shape fitting via linearization",
crossref = "IEEE:2001:ISF",
pages = "66--73",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Agarwal:2001:CMF,
author = "P. K. Agarwal and B. Aronov and M. Sharir",
title = "On the complexity of many faces in arrangements of
circles",
crossref = "IEEE:2001:ISF",
pages = "74--83",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Har-Peled:2001:CM,
author = "S. Har-Peled",
title = "Clustering motion",
crossref = "IEEE:2001:ISF",
pages = "84--93",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Har-Peled:2001:RVD,
author = "S. Har-Peled",
title = "A replacement for {Voronoi} diagrams of near linear
size",
crossref = "IEEE:2001:ISF",
pages = "94--103",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2001:HGB,
author = "B. Barak",
title = "How to go beyond the black-box simulation barrier",
crossref = "IEEE:2001:ISF",
pages = "106--115",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2001:RSZ,
author = "B. Barak and O. Goldreich and S. Goldwasser and Y.
Lindell",
title = "Resettably-sound zero-knowledge and its applications",
crossref = "IEEE:2001:ISF",
pages = "116--125",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gertner:2001:IBT,
author = "Y. Gertner and T. Malkin and O. Reingold",
title = "On the impossibility of basing trapdoor functions on
trapdoor predicates",
crossref = "IEEE:2001:ISF",
pages = "126--135",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Canetti:2001:UCS,
author = "R. Canetti",
title = "Universally composable security: a new paradigm for
cryptographic protocols",
crossref = "IEEE:2001:ISF",
pages = "136--145",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2001:TPD,
author = "A. Gupta and A. Kumar and R. Rastogi",
title = "Traveling with a {PEZ} dispenser (or, routing issues
in {MPLS})",
crossref = "IEEE:2001:ISF",
pages = "148--157",
year = "2001",
bibdate = "Fri Feb 22 06:25:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Andrews:2001:SRS,
author = "M. Andrews and A. Fernandez and A. Goel and L. Zhang",
title = "Source routing and scheduling in packet networks",
crossref = "IEEE:2001:ISF",
pages = "168--177",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Berenbrink:2001:NWS,
author = "P. Berenbrink and T. Friedetzky and L. A. Goldberg",
title = "The natural work-stealing algorithm is stable",
crossref = "IEEE:2001:ISF",
pages = "178--187",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2001:LBP,
author = "M. Alekhnovich and A. A. Razboro",
title = "Lower bounds for polynomial calculus: non-binomial
case",
crossref = "IEEE:2001:ISF",
pages = "190--199",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Impagliazzo:2001:CAD,
author = "R. Impagliazzo and N. Segerlind",
title = "Counting axioms do not polynomially simulate counting
gates",
crossref = "IEEE:2001:ISF",
pages = "200--209",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2001:RAU,
author = "M. Alekhnovich and A. A. Razboro",
title = "Resolution is not automatizable unless {W[P]} is
tractable",
crossref = "IEEE:2001:ISF",
pages = "210--219",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Dantchev:2001:STH,
author = "S. Dantchev and S. Riis",
title = "``Planar'' tautologies hard for resolution",
crossref = "IEEE:2001:ISF",
pages = "220--229",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Fakcharoenphol:2001:PGN,
author = "J. Fakcharoenphol and S. Rao",
title = "Planar graphs, negative weight edges, shortest paths,
and near linear time",
crossref = "IEEE:2001:ISF",
pages = "232--241",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Thorup:2001:COR,
author = "M. Thorup",
title = "Compact oracles for reachability and approximate
distances in planar digraphs",
crossref = "IEEE:2001:ISF",
pages = "242--251",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Hershberger:2001:VPS,
author = "J. Hershberger and Subhash Suri",
title = "{Vickrey} prices and shortest paths: what is an edge
worth?",
crossref = "IEEE:2001:ISF",
pages = "252--259",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
note = "See erratum \cite{Hershberger:2002:ESP}.",
acknowledgement = ack-nhfb,
}
@InProceedings{Demetrescu:2001:FDA,
author = "C. Demetrescu and G. F. Italiano",
title = "Fully dynamic all pairs shortest paths with real edge
weights",
crossref = "IEEE:2001:ISF",
pages = "260--267",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Chakrabarti:2001:ICD,
author = "A. Chakrabarti and Yaoyun Shi and A. Wirth and A.
Yao",
title = "Informational complexity and the direct sum problem
for simultaneous message complexity",
crossref = "IEEE:2001:ISF",
pages = "270--278",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{vanDam:2001:HPA,
author = "W. van Dam and M. Mosca and U. Vazirani",
title = "How powerful is adiabatic quantum computation?",
crossref = "IEEE:2001:ISF",
pages = "279--287",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Klauck:2001:LBQ,
author = "H. Klauck",
title = "Lower bounds for quantum communication complexity",
crossref = "IEEE:2001:ISF",
pages = "288--297",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Comon:2001:CGT,
author = "H. Comon and G. Godoy and R. Nieuwenhuis",
title = "The confluence of ground term rewrite systems is
decidable in polynomial time",
crossref = "IEEE:2001:ISF",
pages = "298--307",
year = "2001",
bibdate = "Fri Feb 22 06:31:26 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@String{j-UNKNOWN = "Unknown journal"}
@InProceedings{Cheriyan:2001:ADM,
author = "J. Cheriyan and H. Karloff and Y. Rabani",
title = "Approximating directed multicuts",
crossref = "IEEE:2001:ISF",
pages = "320--328",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Pal:2001:FLN,
author = "M. Pal and E. Tardos and T. Wexler",
title = "Facility location with nonuniform hard capacities",
crossref = "IEEE:2001:ISF",
pages = "329--338",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Fleischer:2001:IRA,
author = "L. Fleischer and K. Jain and D. P. Williamson",
title = "An iterative rounding $2$-approximation algorithm for
the element connectivity problem",
crossref = "IEEE:2001:ISF",
pages = "339--347",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Chuzhoy:2001:AAJ,
author = "J. Chuzhoy and R. Ostrovsky and Y. Rabani",
title = "Approximation algorithms for the job interval
selection problem and related scheduling problems",
crossref = "IEEE:2001:ISF",
pages = "348--356",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Shpilka:2001:LBM,
author = "A. Shpilka",
title = "Lower bounds for matrix product",
crossref = "IEEE:2001:ISF",
pages = "358--367",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Storjohann:2001:DCF,
author = "A. Storjohann",
title = "Deterministic computation of the {Frobenius} form",
crossref = "IEEE:2001:ISF",
pages = "368--377",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Burgisser:2001:CFM,
author = "P. Burgisser",
title = "The complexity of factors of multivariate
polynomials",
crossref = "IEEE:2001:ISF",
pages = "378--385",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{McConnell:2001:LTR,
author = "R. M. McConnell",
title = "Linear-time recognition of circular-arc graphs",
crossref = "IEEE:2001:ISF",
pages = "386--394",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Bartal:2001:RTT,
author = "Y. Bartal and B. Bollobas and M. Mendel",
title = "A {Ramsey}-type theorem for metric spaces and its
applications for metrical task systems and related
problems",
crossref = "IEEE:2001:ISF",
pages = "396--405",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Meyerson:2001:DNI,
author = "A. Meyerson and K. Munagala and S. Plotkin",
title = "Designing networks incrementally",
crossref = "IEEE:2001:ISF",
pages = "406--415",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2001:SSS,
author = "A. Gupta and A. Kumar",
title = "Sorting and selection with structured costs",
crossref = "IEEE:2001:ISF",
pages = "416--425",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Meyerson:2001:OFL,
author = "A. Meyerson",
title = "Online facility location",
crossref = "IEEE:2001:ISF",
pages = "426--431",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:2001:TSL,
author = "N. Alon",
title = "Testing subgraphs in large graphs",
crossref = "IEEE:2001:ISF",
pages = "434--439",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Batu:2001:TRV,
author = "T. Batu and E. Fischer and L. Fortnow and R. Kumar and
R. Rubinfeld and P. White",
title = "Testing random variables for independence and
identity",
crossref = "IEEE:2001:ISF",
pages = "442--451",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@String{j-UNKNOWN = "Unknown journal"}
@InProceedings{Goldreich:2001:TTR,
author = "O. Goldreich and L. Trevisan",
title = "Three theorems regarding testing graph properties",
crossref = "IEEE:2001:ISF",
pages = "460--469",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Roughgarden:2001:DNS,
author = "T. Roughgarden",
title = "Designing networks for selfish users is hard",
crossref = "IEEE:2001:ISF",
pages = "472--481",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Archer:2001:TMO,
author = "A. Archer and E. Tardos",
title = "Truthful mechanisms for one-parameter agents",
crossref = "IEEE:2001:ISF",
pages = "482--491",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Pandurangan:2001:BLD,
author = "G. Pandurangan and P. Raghavan and E. Upfal",
title = "Building low-diameter {P2P} networks",
crossref = "IEEE:2001:ISF",
pages = "492--499",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Achlioptas:2001:WSH,
author = "D. Achlioptas and A. Fiat and A. R. Karlin and F.
McSherry",
title = "{Web} search via hub synthesis",
crossref = "IEEE:2001:ISF",
pages = "500--509",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Aiello:2001:REM,
author = "W. Aiello and Fan Chung and Linyuan Lu",
title = "Random evolution in massive graphs",
crossref = "IEEE:2001:ISF",
pages = "510--519",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kolliopoulos:2001:TAR,
author = "S. G. Kolliopoulos and N. E. Young",
title = "Tight approximation results for general covering
integer programs",
crossref = "IEEE:2001:ISF",
pages = "522--528",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{McSherry:2001:SPR,
author = "F. McSherry",
title = "Spectral partitioning of random graphs",
crossref = "IEEE:2001:ISF",
pages = "529--537",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Young:2001:SPA,
author = "N. E. Young",
title = "Sequential and parallel algorithms for mixed packing
and covering",
crossref = "IEEE:2001:ISF",
pages = "538--546",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Szabo:2001:USO,
author = "T. Szabo and E. Welzl",
title = "Unique sink orientations of cubes",
crossref = "IEEE:2001:ISF",
pages = "547--555",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Bohman:2001:ADP,
author = "T. Bohman and A. Frieze",
title = "Arc-disjoint paths in expander digraphs",
crossref = "IEEE:2001:ISF",
pages = "558--567",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Kenyon:2001:GDT,
author = "C. Kenyon and E. Mossel and Y. Peres",
title = "{Glauber} dynamics on trees and hyperbolic graphs",
crossref = "IEEE:2001:ISF",
pages = "568--578",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Dyer:2001:RCG,
author = "M. Dyer and A. Frieze",
title = "Randomly colouring graphs with lower bounds on girth
and maximum degree",
crossref = "IEEE:2001:ISF",
pages = "579--587",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Srinivasan:2001:DLS,
author = "A. Srinivasan",
title = "Distributions on level-sets with applications to
approximation algorithms",
crossref = "IEEE:2001:ISF",
pages = "588--597",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@String{j-UNKNOWN = "Unknown journal"}
@InProceedings{Hastad:2001:QEP,
author = "J. Hastad and S. Khot",
title = "Query efficient {PCPs} with perfect completeness",
crossref = "IEEE:2001:ISF",
pages = "610--619",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Cai:2001:Z,
author = "Jin-Yi Cai",
title = "{S$_2$ ZPP$^{NP}$}",
crossref = "IEEE:2001:ISF",
pages = "620--628",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:2001:SDP,
author = "N. Alon and A. Lubotzky and A. Wigderson",
title = "Semi-direct product in groups and zig-zag product in
graphs: connections and applications",
crossref = "IEEE:2001:ISF",
pages = "630--637",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Ta-Shma:2001:ERM,
author = "A. Ta-Shma and D. Zuckerman and S. Safra",
title = "Extractors from {Reed-Muller} codes",
crossref = "IEEE:2001:ISF",
pages = "638--647",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Shaltiel:2001:SEA,
author = "R. Shaltiel and C. Umans",
title = "Simple extractors for all min-entropies and a new
pseudo-random generator",
crossref = "IEEE:2001:ISF",
pages = "648--657",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Guruswami:2001:EBC,
author = "V. Guruswami and P. Indyk",
title = "Expander-based constructions of efficiently decodable
codes",
crossref = "IEEE:2001:ISF",
pages = "658--667",
year = "2001",
bibdate = "Fri Feb 22 06:31:27 MST 2002",
bibsource = "http://ieeexplore.ieee.org/",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldreich:2002:ZKA,
author = "O. Goldreich",
title = "Zero-knowledge: abstract of a tutorial",
crossref = "IEEE:2002:PAI",
pages = "3--3",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181876&count=82&index=1;
http://ieeexplore.ieee.org/iel5/8411/26517/01181876.pdf?isnumber=26517&prod=CNF&arnumber=1181876&arSt=+3&ared=&arAuthor=Goldreich%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Vadhan:2002:RET,
author = "S. P. Vadhan",
title = "Randomness extractors and their many guises",
crossref = "IEEE:2002:PAI",
pages = "9--9",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181877&count=82&index=2;
http://ieeexplore.ieee.org/iel5/8411/26517/01181877.pdf?isnumber=26517&prod=CNF&arnumber=1181877&arSt=+9&ared=&arAuthor=Vadhan%2C+S.P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldreich:2002:LTC,
author = "O. Goldreich and M. Sudan",
title = "Locally testable codes and {PCPs} of almost-linear
length",
crossref = "IEEE:2002:PAI",
pages = "13--22",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181878&count=82&index=3;
http://ieeexplore.ieee.org/iel5/8411/26517/01181878.pdf?isnumber=26517&prod=CNF&arnumber=1181878&arSt=+13&ared=+22&arAuthor=Goldreich%2C+O.%3B+Sudan%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Khot:2002:HRC,
author = "S. Khot",
title = "Hardness results for coloring $3$-colorable
$3$-uniform hypergraphs",
crossref = "IEEE:2002:PAI",
pages = "23--32",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181879&count=82&index=4;
http://ieeexplore.ieee.org/iel5/8411/26517/01181879.pdf?isnumber=26517&prod=CNF&arnumber=1181879&arSt=+23&ared=+32&arAuthor=Khot%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dinur:2002:HUH,
author = "I. Dinur and O. Regev and C. Smyth",
title = "The hardness of $3$-uniform hypergraph coloring",
crossref = "IEEE:2002:PAI",
pages = "33--40",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181880&count=82&index=5;
http://ieeexplore.ieee.org/iel5/8411/26517/01181880.pdf?isnumber=26517&prod=CNF&arnumber=1181880&arSt=+33&ared=+40&arAuthor=Dinur%2C+I.%3B+Regev%2C+O.%3B+Smyth%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Racke:2002:MCG,
author = "H. Racke",
title = "Minimizing congestion in general networks",
crossref = "IEEE:2002:PAI",
pages = "43--52",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181881&count=82&index=6;
http://ieeexplore.ieee.org/iel5/8411/26517/01181881.pdf?isnumber=26517&prod=CNF&arnumber=1181881&arSt=+43&ared=+52&arAuthor=Racke%2C+H.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alstrup:2002:SIU,
author = "S. Alstrup and T. Rauhe",
title = "Small induced-universal graphs and compact implicit
graph representations",
crossref = "IEEE:2002:PAI",
pages = "53--62",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181882&count=82&index=7;
http://ieeexplore.ieee.org/iel5/8411/26517/01181882.pdf?isnumber=26517&prod=CNF&arnumber=1181882&arSt=+53&ared=+62&arAuthor=Alstrup%2C+S.%3B+Rauhe%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kowalski:2002:DBT,
author = "D. R. Kowalski and A. Pelc",
title = "Deterministic broadcasting time in radio networks of
unknown topology",
crossref = "IEEE:2002:PAI",
pages = "63--72",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181883&count=82&index=8;
http://ieeexplore.ieee.org/iel5/8411/26517/01181883.pdf?isnumber=26517&prod=CNF&arnumber=1181883&arSt=+63&ared=+72&arAuthor=Kowalski%2C+D.R.%3B+Pelc%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:2002:EUN,
author = "N. Alon and M. Capalbo",
title = "Explicit unique-neighbor expanders",
crossref = "IEEE:2002:PAI",
pages = "73--79",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181884&count=82&index=9;
http://ieeexplore.ieee.org/iel5/8411/26517/01181884.pdf?isnumber=26517&prod=CNF&arnumber=1181884&arSt=+73&ared=+79&arAuthor=Alon%2C+N.%3B+Capalbo%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Czumaj:2002:ACP,
author = "A. Czumaj and C. Sohler",
title = "Abstract combinatorial programs and efficient property
testers",
crossref = "IEEE:2002:PAI",
pages = "83--92",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181885&count=82&index=10;
http://ieeexplore.ieee.org/iel5/8411/26517/01181885.pdf?isnumber=26517&prod=CNF&arnumber=1181885&arSt=+83&ared=+92&arAuthor=Czumaj%2C+A.%3B+Sohler%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bogdanov:2002:LBT,
author = "A. Bogdanov and K. Obata and L. Trevisan",
title = "A lower bound for testing $3$-colorability in
bounded-degree graphs",
crossref = "IEEE:2002:PAI",
pages = "93--102",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181886&count=82&index=11;
http://ieeexplore.ieee.org/iel5/8411/26517/01181886.pdf?isnumber=26517&prod=CNF&arnumber=1181886&arSt=+93&ared=+102&arAuthor=Bogdanov%2C+A.%3B+Obata%2C+K.%3B+Trevisan%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Fischer:2002:TJC,
author = "E. Fischer and G. Kindler and D. Ron and S. Safra and
A. Samorodnitsky",
title = "Testing juntas [combinatorial property testing]",
crossref = "IEEE:2002:PAI",
pages = "103--112",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181887&count=82&index=12;
http://ieeexplore.ieee.org/iel5/8411/26517/01181887.pdf?isnumber=26517&prod=CNF&arnumber=1181887&arSt=+103&ared=+112&arAuthor=Fischer%2C+E.%3B+Kindler%2C+G.%3B+Ron%2C+D.%3B+Safra%2C+S.%3B+Samorodnitsky%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Vempala:2002:SAL,
author = "S. Vempala and G. Wang",
title = "A spectral algorithm for learning mixtures of
distributions",
crossref = "IEEE:2002:PAI",
pages = "113--122",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181888&count=82&index=13;
http://ieeexplore.ieee.org/iel5/8411/26517/01181888.pdf?isnumber=26517&prod=CNF&arnumber=1181888&arSt=+113&ared=+122&arAuthor=Vempala%2C+S.%3B+Wang%2C+G.",
acknowledgement = ack-nhfb,
}
@InProceedings{Thorup:2002:EBP,
author = "M. Thorup",
title = "Equivalence between priority queues and sorting",
crossref = "IEEE:2002:PAI",
pages = "125--134",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181889&count=82&index=14;
http://ieeexplore.ieee.org/iel5/8411/26517/01181889.pdf?isnumber=26517&prod=CNF&arnumber=1181889&arSt=+125&ared=+134&arAuthor=Thorup%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Han:2002:ISS,
author = "Yijie Han and M. Thorup",
title = "Integer sorting in {$O(n \sqrt(\log \log n))$}
expected time and linear space",
crossref = "IEEE:2002:PAI",
pages = "135--144",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181890&count=82&index=15;
http://ieeexplore.ieee.org/iel5/8411/26517/01181890.pdf?isnumber=26517&prod=CNF&arnumber=1181890&arSt=+135&ared=+144&arAuthor=Yijie+Han%3B+Thorup%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Franceschini:2002:IBT,
author = "G. Franceschini and R. Grossi and J. I. Munro and L.
Pagli",
title = "Implicit {B}-trees: {New} results for the dictionary
problem",
crossref = "IEEE:2002:PAI",
pages = "145--154",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181891&count=82&index=16;
http://ieeexplore.ieee.org/iel5/8411/26517/01181891.pdf?isnumber=26517&prod=CNF&arnumber=1181891&arSt=+145&ared=+154&arAuthor=Franceschini%2C+G.%3B+Grossi%2C+R.%3B+Munro%2C+J.I.%3B+Pagli%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Pettie:2002:IAS,
author = "S. Pettie",
title = "An inverse-{Ackermann} style lower bound for the
online minimum spanning tree verification problem",
crossref = "IEEE:2002:PAI",
pages = "155--163",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181892&count=82&index=17;
http://ieeexplore.ieee.org/iel5/8411/26517/01181892.pdf?isnumber=26517&prod=CNF&arnumber=1181892&arSt=+155&ared=+163&arAuthor=Pettie%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bshouty:2002:PPO,
author = "N. H. Bshouty and D. Gavinsky",
title = "{PAC} $=$ {PAExact} and other equivalent models in
learning",
crossref = "IEEE:2002:PAI",
pages = "167--176",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181893&count=82&index=18;
http://ieeexplore.ieee.org/iel5/8411/26517/01181893.pdf?isnumber=26517&prod=CNF&arnumber=1181893&arSt=+167&ared=+176&arAuthor=Bshouty%2C+N.H.%3B+Gavinsky%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Klivans:2002:LIT,
author = "A. R. Klivans and R. O'Donnell",
title = "Learning intersections and thresholds of halfspaces",
crossref = "IEEE:2002:PAI",
pages = "177--186",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181894&count=82&index=19;
http://ieeexplore.ieee.org/iel5/8411/26517/01181894.pdf?isnumber=26517&prod=CNF&arnumber=1181894&arSt=+177&ared=+186&arAuthor=Klivans%2C+A.R.%3B+O%27Donnell%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Vovk:2002:LCM,
author = "V. Vovk",
title = "On-line confidence machines are well-calibrated",
crossref = "IEEE:2002:PAI",
pages = "187--196",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181895&count=82&index=20;
http://ieeexplore.ieee.org/iel5/8411/26517/01181895.pdf?isnumber=26517&prod=CNF&arnumber=1181895&arSt=+187&ared=+196&arAuthor=Vovk%2C+V.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alon:2002:LHM,
author = "N. Alon and R. Beigel and S. Kasif and S. Rudich and
B. Sudakov",
title = "Learning a hidden matching",
crossref = "IEEE:2002:PAI",
pages = "197--206",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181943&count=82&index=21;
http://ieeexplore.ieee.org/iel5/8411/26517/01181943.pdf?isnumber=26517&prod=CNF&arnumber=1181943&arSt=+197&ared=+206&arAuthor=Alon%2C+N.%3B+Beigel%2C+R.%3B+Kasif%2C+S.%3B+Rudich%2C+S.%3B+Sudakov%2C+B.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bar-Yossef:2002:ISA,
author = "Z. Bar-Yossef and T. S. Jayram and R. Kumar and D.
Sivakumar",
title = "An information statistics approach to data stream and
communication complexity",
crossref = "IEEE:2002:PAI",
pages = "209--218",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181944&count=82&index=22;
http://ieeexplore.ieee.org/iel5/8411/26517/01181944.pdf?isnumber=26517&prod=CNF&arnumber=1181944&arSt=+209&ared=+218&arAuthor=Bar-Yossef%2C+Z.%3B+Jayram%2C+T.S.%3B+Kumar%2C+R.%3B+Sivakumar%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Ciriani:2002:SOT,
author = "V. Ciriani and P. Ferragina and F. Luccio and S.
Muthukrishnan",
title = "Static optimality theorem for external memory string
access",
crossref = "IEEE:2002:PAI",
pages = "219--227",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181945&count=82&index=23;
http://ieeexplore.ieee.org/iel5/8411/26517/01181945.pdf?isnumber=26517&prod=CNF&arnumber=1181945&arSt=+219&ared=+227&arAuthor=Ciriani%2C+V.%3B+Ferragina%2C+P.%3B+Luccio%2C+F.%3B+Muthukrishnan%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Gafni:2002:SAC,
author = "E. Gafni",
title = "A simple algorithmic characterization of uniform
solvability",
crossref = "IEEE:2002:PAI",
pages = "228--237",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181946&count=82&index=24;
http://ieeexplore.ieee.org/iel5/8411/26517/01181946.pdf?isnumber=26517&prod=CNF&arnumber=1181946&arSt=+228&ared=+237&arAuthor=Gafni%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bansal:2002:CC,
author = "N. Bansal and A. Blum and S. Chawla",
title = "Correlation clustering",
crossref = "IEEE:2002:PAI",
pages = "238--247",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181947&count=82&index=25;
http://ieeexplore.ieee.org/iel5/8411/26517/01181947.pdf?isnumber=26517&prod=CNF&arnumber=1181947&arSt=+238&ared=+247&arAuthor=Bansal%2C+N.%3B+Blum%2C+A.%3B+Chawla%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Feldman:2002:DTL,
author = "J. Feldman and D. R. Karger",
title = "Decoding turbo-like codes via linear programming",
crossref = "IEEE:2002:PAI",
pages = "251--260",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181948&count=82&index=26;
http://ieeexplore.ieee.org/iel5/8411/26517/01181948.pdf?isnumber=26517&prod=CNF&arnumber=1181948&arSt=+251&ared=+260&arAuthor=Feldman%2C+J.%3B+Karger%2C+D.R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Beimel:2002:BSB,
author = "A. Beimel and Y. Ishai and E. Kushilevitz and J.-F.
Raymond",
title = "Breaking the {$O(n^{1/(2k-1)})$} barrier for
information-theoretic {Private Information Retrieval}",
crossref = "IEEE:2002:PAI",
pages = "261--270",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181949&count=82&index=27;
http://ieeexplore.ieee.org/iel5/8411/26517/01181949.pdf?isnumber=26517&prod=CNF&arnumber=1181949&arSt=+261&ared=+270&arAuthor=Beimel%2C+A.%3B+Ishai%2C+Y.%3B+Kushilevitz%2C+E.%3B+Raymond%2C+J.-F.",
acknowledgement = ack-nhfb,
}
@InProceedings{Luby:2002:LC,
author = "M. Luby",
title = "{LT} codes",
crossref = "IEEE:2002:PAI",
pages = "271--280",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181950&count=82&index=28;
http://ieeexplore.ieee.org/iel5/8411/26517/01181950.pdf?isnumber=26517&prod=CNF&arnumber=1181950&arSt=+271&ared=+280&arAuthor=Luby%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Feige:2002:GTV,
author = "U. Feige and M. Langberg and G. Schechtman",
title = "Graphs with tiny vector chromatic numbers and huge
chromatic numbers",
crossref = "IEEE:2002:PAI",
pages = "283--292",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181951&count=82&index=29;
http://ieeexplore.ieee.org/iel5/8411/26517/01181951.pdf?isnumber=26517&prod=CNF&arnumber=1181951&arSt=+283&ared=+292&arAuthor=Feige%2C+U.%3B+Langberg%2C+M.%3B+Schechtman%2C+G.",
acknowledgement = ack-nhfb,
}
@InProceedings{Andrews:2002:STV,
author = "M. Andrews and L. Zhang",
title = "Scheduling over a time-varying user-dependent channel
with applications to high speed wireless data",
crossref = "IEEE:2002:PAI",
pages = "293--302",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181952&count=82&index=30;
http://ieeexplore.ieee.org/iel5/8411/26517/01181952.pdf?isnumber=26517&prod=CNF&arnumber=1181952&arSt=+293&ared=+302&arAuthor=Andrews%2C+M.%3B+Zhang%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Garg:2002:LEE,
author = "N. Garg and N. E. Young",
title = "On-line end-to-end congestion control",
crossref = "IEEE:2002:PAI",
pages = "303--310",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181953&count=82&index=31;
http://ieeexplore.ieee.org/iel5/8411/26517/01181953.pdf?isnumber=26517&prod=CNF&arnumber=1181953&arSt=+303&ared=+310&arAuthor=Garg%2C+N.%3B+Young%2C+N.E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Arora:2002:PIG,
author = "S. Arora and B. Bollobas and L. Lovasz",
title = "Proving integrality gaps without knowing the linear
program",
crossref = "IEEE:2002:PAI",
pages = "313--322",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181954&count=82&index=32;
http://ieeexplore.ieee.org/iel5/8411/26517/01181954.pdf?isnumber=26517&prod=CNF&arnumber=1181954&arSt=+313&ared=+322&arAuthor=Arora%2C+S.%3B+Bollobas%2C+B.%3B+Lovasz%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Gandhi:2002:DRB,
author = "R. Gandhi and S. Khuller and S. Parthasarathy and A.
Srinivasan",
title = "Dependent rounding in bipartite graphs",
crossref = "IEEE:2002:PAI",
pages = "323--332",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181955&count=82&index=33;
http://ieeexplore.ieee.org/iel5/8411/26517/01181955.pdf?isnumber=26517&prod=CNF&arnumber=1181955&arSt=+323&ared=+332&arAuthor=Gandhi%2C+R.%3B+Khuller%2C+S.%3B+Parthasarathy%2C+S.%3B+Srinivasan%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kumar:2002:CFA,
author = "A. Kumar and A. Gupta and T. Roughgarden",
title = "A constant-factor approximation algorithm for the
multicommodity rent-or-buy problem",
crossref = "IEEE:2002:PAI",
pages = "333--342",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181956&count=82&index=34;
http://ieeexplore.ieee.org/iel5/8411/26517/01181956.pdf?isnumber=26517&prod=CNF&arnumber=1181956&arSt=+333&ared=+342&arAuthor=Kumar%2C+A.%3B+Gupta%2C+A.%3B+Roughgarden%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2002:CRC,
author = "B. Barak",
title = "Constant-round coin-tossing with a man in the middle
or realizing the shared random string model",
crossref = "IEEE:2002:PAI",
pages = "345--355",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181957&count=82&index=35;
http://ieeexplore.ieee.org/iel5/8411/26517/01181957.pdf?isnumber=26517&prod=CNF&arnumber=1181957&arSt=+345&ared=+355&arAuthor=Barak%2C+B.",
acknowledgement = ack-nhfb,
}
@InProceedings{Micciancio:2002:GCK,
author = "D. Micciancio",
title = "Generalized compact knapsacks, cyclic lattices, and
efficient one-way functions from worst-case complexity
assumptions",
crossref = "IEEE:2002:PAI",
pages = "356--365",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181960&count=82&index=36;
http://ieeexplore.ieee.org/iel5/8411/26517/01181960.pdf?isnumber=26517&prod=CNF&arnumber=1181960&arSt=+356&ared=+365&arAuthor=Micciancio%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Prabhakaran:2002:CZK,
author = "M. Prabhakaran and A. Rosen and A. Sahai",
title = "Concurrent zero knowledge with logarithmic
round-complexity",
crossref = "IEEE:2002:PAI",
pages = "366--375",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181961&count=82&index=37;
http://ieeexplore.ieee.org/iel5/8411/26517/01181961.pdf?isnumber=26517&prod=CNF&arnumber=1181961&arSt=+366&ared=+375&arAuthor=Prabhakaran%2C+M.%3B+Rosen%2C+A.%3B+Sahai%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dodis:2002:NUO,
author = "Y. Dodis and J. Spencer",
title = "On the (non)universality of the one-time pad",
crossref = "IEEE:2002:PAI",
pages = "376--385",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181962&count=82&index=38;
http://ieeexplore.ieee.org/iel5/8411/26517/01181962.pdf?isnumber=26517&prod=CNF&arnumber=1181962&arSt=+376&ared=+385&arAuthor=Dodis%2C+Y.%3B+Spencer%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Devanur:2002:MEP,
author = "N. R. Devanur and C. H. Papadimitriou and A. Saberi
and V. V. Vazirani",
title = "Market equilibrium via a primal-dual-type algorithm",
crossref = "IEEE:2002:PAI",
pages = "389--395",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181963&count=82&index=39;
http://ieeexplore.ieee.org/iel5/8411/26517/01181963.pdf?isnumber=26517&prod=CNF&arnumber=1181963&arSt=+389&ared=+395&arAuthor=Devanur%2C+N.R.%3B+Papadimitriou%2C+C.H.%3B+Saberi%2C+A.%3B+Vazirani%2C+V.V.",
acknowledgement = ack-nhfb,
}
@InProceedings{Ronen:2002:HOA,
author = "A. Ronen and A. Saberi",
title = "On the hardness of optimal auctions",
crossref = "IEEE:2002:PAI",
pages = "396--405",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181964&count=82&index=40;
http://ieeexplore.ieee.org/iel5/8411/26517/01181964.pdf?isnumber=26517&prod=CNF&arnumber=1181964&arSt=+396&ared=+405&arAuthor=Ronen%2C+A.%3B+Saberi%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Blumrosen:2002:ASB,
author = "L. Blumrosen and N. Nisan",
title = "Auctions with severely bounded communication",
crossref = "IEEE:2002:PAI",
pages = "406--415",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181965&count=82&index=41;
http://ieeexplore.ieee.org/iel5/8411/26517/01181965.pdf?isnumber=26517&prod=CNF&arnumber=1181965&arSt=+406&ared=+415&arAuthor=Blumrosen%2C+L.%3B+Nisan%2C+N.",
acknowledgement = ack-nhfb,
}
@InProceedings{Vetta:2002:NEC,
author = "A. Vetta",
title = "Nash equilibria in competitive societies, with
applications to facility location, traffic routing and
auctions",
crossref = "IEEE:2002:PAI",
pages = "416--425",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181966&count=82&index=42;
http://ieeexplore.ieee.org/iel5/8411/26517/01181966.pdf?isnumber=26517&prod=CNF&arnumber=1181966&arSt=+416&ared=+425&arAuthor=Vetta%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Jain:2002:PIQ,
author = "R. Jain and J. Radhakrishnan and P. Sen",
title = "Privacy and interaction in quantum communication
complexity and a theorem about the relative entropy of
quantum states",
crossref = "IEEE:2002:PAI",
pages = "429--438",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181967&count=82&index=43;
http://ieeexplore.ieee.org/iel5/8411/26517/01181967.pdf?isnumber=26517&prod=CNF&arnumber=1181967&arSt=+429&ared=+438&arAuthor=Jain%2C+R.%3B+Radhakrishnan%2C+J.%3B+Sen%2C+P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2002:LDE,
author = "M. Alekhnovich",
title = "Linear {Diophantine} equations over polynomials and
soft decoding of {Reed--Solomon} codes",
crossref = "IEEE:2002:PAI",
pages = "439--448",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181968&count=82&index=44;
http://ieeexplore.ieee.org/iel5/8411/26517/01181968.pdf?isnumber=26517&prod=CNF&arnumber=1181968&arSt=+439&ared=+448&arAuthor=Alekhnovich%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Barnum:2002:AQM,
author = "H. Barnum and C. Crepeau and D. Gottesman and A. Smith
and A. Tapp",
title = "Authentication of quantum messages",
crossref = "IEEE:2002:PAI",
pages = "449--458",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181969&count=82&index=45;
http://ieeexplore.ieee.org/iel5/8411/26517/01181969.pdf?isnumber=26517&prod=CNF&arnumber=1181969&arSt=+449&ared=+458&arAuthor=Barnum%2C+H.%3B+Crepeau%2C+C.%3B+Gottesman%2C+D.%3B+Smith%2C+A.%3B+Tapp%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Watrous:2002:LPQ,
author = "J. Watrous",
title = "Limits on the power of quantum statistical
zero-knowledge",
crossref = "IEEE:2002:PAI",
pages = "459--468",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181970&count=82&index=46;
http://ieeexplore.ieee.org/iel5/8411/26517/01181970.pdf?isnumber=26517&prod=CNF&arnumber=1181970&arSt=+459&ared=+468&arAuthor=Watrous%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kempe:2002:PIR,
author = "D. Kempe and J. Kleinberg",
title = "Protocols and impossibility results for gossip-based
communication mechanisms",
crossref = "IEEE:2002:PAI",
pages = "471--480",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181971&count=82&index=47;
http://ieeexplore.ieee.org/iel5/8411/26517/01181971.pdf?isnumber=26517&prod=CNF&arnumber=1181971&arSt=+471&ared=+480&arAuthor=Kempe%2C+D.%3B+Kleinberg%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chuzhoy:2002:CPH,
author = "J. Chuzhoy and J. S. Naor",
title = "Covering problems with hard capacities",
crossref = "IEEE:2002:PAI",
pages = "481--489",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181972&count=82&index=48;
http://ieeexplore.ieee.org/iel5/8411/26517/01181972.pdf?isnumber=26517&prod=CNF&arnumber=1181972&arSt=+481&ared=+489&arAuthor=Chuzhoy%2C+J.%3B+Naor%2C+J.S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Caprara:2002:PDB,
author = "A. Caprara",
title = "Packing 2-dimensional bins in harmony",
crossref = "IEEE:2002:PAI",
pages = "490--499",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181973&count=82&index=49;
http://ieeexplore.ieee.org/iel5/8411/26517/01181973.pdf?isnumber=26517&prod=CNF&arnumber=1181973&arSt=+490&ared=+499&arAuthor=Caprara%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Garg:2002:FAA,
author = "N. Garg and R. Khandekar",
title = "Fast approximation algorithms for fractional {Steiner}
forest and related problems",
crossref = "IEEE:2002:PAI",
pages = "500--509",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181974&count=82&index=50;
http://ieeexplore.ieee.org/iel5/8411/26517/01181974.pdf?isnumber=26517&prod=CNF&arnumber=1181974&arSt=+500&ared=+509&arAuthor=Garg%2C+N.%3B+Khandekar%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Shi:2002:QLB,
author = "Yaoyun Shi",
title = "Quantum lower bounds for the collision and the element
distinctness problems",
crossref = "IEEE:2002:PAI",
pages = "513--519",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181975&count=82&index=51;
http://ieeexplore.ieee.org/iel5/8411/26517/01181975.pdf?isnumber=26517&prod=CNF&arnumber=1181975&arSt=+513&ared=+519&arAuthor=Yaoyun+Shi",
acknowledgement = ack-nhfb,
}
@InProceedings{Regev:2002:QCL,
author = "O. Regev",
title = "Quantum computation and lattice problems",
crossref = "IEEE:2002:PAI",
pages = "520--529",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181976&count=82&index=52;
http://ieeexplore.ieee.org/iel5/8411/26517/01181976.pdf?isnumber=26517&prod=CNF&arnumber=1181976&arSt=+520&ared=+529&arAuthor=Regev%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Adleman:2002:DSA,
author = "L. Adleman and J. Kari and L. Kari and D. Reishus",
title = "On the decidability of self-assembly of infinite
ribbons",
crossref = "IEEE:2002:PAI",
pages = "530--537",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181977&count=82&index=53;
http://ieeexplore.ieee.org/iel5/8411/26517/01181977.p