%%% -*-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.pdf?isnumber=26517&prod=CNF&arnumber=1181977&arSt=+530&ared=+537&arAuthor=Adleman%2C+L.%3B+Kari%2C+J.%3B+Kari%2C+L.%3B+Reishus%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Flum:2002:PCC,
author = "J. Flum and M. Grohe",
title = "The parameterized complexity of counting problems",
crossref = "IEEE:2002:PAI",
pages = "538--547",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181978&count=82&index=54;
http://ieeexplore.ieee.org/iel5/8411/26517/01181978.pdf?isnumber=26517&prod=CNF&arnumber=1181978&arSt=+538&ared=+547&arAuthor=Flum%2C+J.%3B+Grohe%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Charikar:2002:DRS,
author = "M. Charikar and A. Sahai",
title = "Dimension reduction in the $\ell_1$ norm",
crossref = "IEEE:2002:PAI",
pages = "551--560",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181979&count=82&index=55;
http://ieeexplore.ieee.org/iel5/8411/26517/01181979.pdf?isnumber=26517&prod=CNF&arnumber=1181979&arSt=+551&ared=+560&arAuthor=Charikar%2C+M.%3B+Sahai%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Varadarajan:2002:ARP,
author = "K. R. Varadarajan and S. Venkatesh and Jiawei Zhang",
title = "On approximating the radii of point sets in high
dimensions",
crossref = "IEEE:2002:PAI",
pages = "561--569",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181980&count=82&index=56;
http://ieeexplore.ieee.org/iel5/8411/26517/01181980.pdf?isnumber=26517&prod=CNF&arnumber=1181980&arSt=+561&ared=+569&arAuthor=Varadarajan%2C+K.R.%3B+Venkatesh%2C+S.%3B+Jiawei+Zhang",
acknowledgement = ack-nhfb,
}
@InProceedings{Chan:2002:LDL,
author = "T. M. Chan",
title = "Low-dimensional linear programming with violations",
crossref = "IEEE:2002:PAI",
pages = "570--579",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181981&count=82&index=57;
http://ieeexplore.ieee.org/iel5/8411/26517/01181981.pdf?isnumber=26517&prod=CNF&arnumber=1181981&arSt=+570&ared=+579&arAuthor=Chan%2C+T.M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Buresh-Oppenheim:2002:BDF,
author = "J. Buresh-Oppenheim and P. Beame and T. Pitassi and R.
Raz and A. Sabharwal",
title = "Bounded-depth {Frege} lower bounds for weaker
pigeonhole principles",
crossref = "IEEE:2002:PAI",
pages = "583--592",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181982&count=82&index=58;
http://ieeexplore.ieee.org/iel5/8411/26517/01181982.pdf?isnumber=26517&prod=CNF&arnumber=1181982&arSt=+583&ared=+592&arAuthor=Buresh-Oppenheim%2C+J.%3B+Beame%2C+P.%3B+Pitassi%2C+T.%3B+Raz%2C+R.%3B+Sabharwal%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2002:SBW,
author = "M. Alekhnovich and A. A. Razborov",
title = "Satisfiability, branch-width and {Tseitin}
tautologies",
crossref = "IEEE:2002:PAI",
pages = "593--603",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181983&count=82&index=59;
http://ieeexplore.ieee.org/iel5/8411/26517/01181983.pdf?isnumber=26517&prod=CNF&arnumber=1181983&arSt=+593&ared=+603&arAuthor=Alekhnovich%2C+M.%3B+Razborov%2C+A.A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Segerlind:2002:SLS,
author = "N. Segerlind and S. Buss and R. Impagliazzo",
title = "Switching lemma for small restrictions and lower
bounds for {$k$-DNF} resolution",
crossref = "IEEE:2002:PAI",
pages = "604--613",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181984&count=82&index=60;
http://ieeexplore.ieee.org/iel5/8411/26517/01181984.pdf?isnumber=26517&prod=CNF&arnumber=1181984&arSt=+604&ared=+613&arAuthor=Segerlind%2C+N.%3B+Buss%2C+S.%3B+Impagliazzo%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Brodal:2002:DPC,
author = "G. S. Brodal and R. Jacob",
title = "Dynamic planar convex hull",
crossref = "IEEE:2002:PAI",
pages = "617--626",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181985&count=82&index=61;
http://ieeexplore.ieee.org/iel5/8411/26517/01181985.pdf?isnumber=26517&prod=CNF&arnumber=1181985&arSt=+617&ared=+626&arAuthor=Brodal%2C+G.S.%3B+Jacob%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{deVerdiere:2002:OSL,
author = "E. C. de Verdiere and F. Lazarus",
title = "Optimal system of loops on an orientable surface",
crossref = "IEEE:2002:PAI",
pages = "627--636",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181986&count=82&index=62;
http://ieeexplore.ieee.org/iel5/8411/26517/01181986.pdf?isnumber=26517&prod=CNF&arnumber=1181986&arSt=+627&ared=+636&arAuthor=de+Verdiere%2C+E.C.%3B+Lazarus%2C+F.",
acknowledgement = ack-nhfb,
}
@InProceedings{Koltun:2002:PTO,
author = "V. Koltun and M. Sharir",
title = "The partition technique for overlays of envelopes",
crossref = "IEEE:2002:PAI",
pages = "637--646",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181989&count=82&index=63;
http://ieeexplore.ieee.org/iel5/8411/26517/01181989.pdf?isnumber=26517&prod=CNF&arnumber=1181989&arSt=+637&ared=+646&arAuthor=Koltun%2C+V.%3B+Sharir%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bulatov:2002:DTC,
author = "A. A. Bulatov",
title = "A dichotomy theorem for constraints on a three-element
set",
crossref = "IEEE:2002:PAI",
pages = "649--658",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181990&count=82&index=64;
http://ieeexplore.ieee.org/iel5/8411/26517/01181990.pdf?isnumber=26517&prod=CNF&arnumber=1181990&arSt=+649&ared=+658&arAuthor=Bulatov%2C+A.A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Burgisser:2002:LBB,
author = "P. Burgisser and M. Lotz",
title = "Lower bounds on the bounded coefficient complexity of
bilinear maps",
crossref = "IEEE:2002:PAI",
pages = "659--668",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181991&count=82&index=65;
http://ieeexplore.ieee.org/iel5/8411/26517/01181991.pdf?isnumber=26517&prod=CNF&arnumber=1181991&arSt=+659&ared=+668&arAuthor=Burgisser%2C+P.%3B+Lotz%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Allender:2002:PRS,
author = "E. Allender and H. Buhrman and M. Koucky and D. van
Melkebeek and D. Ronneburger",
title = "Power from random strings",
crossref = "IEEE:2002:PAI",
pages = "669--678",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181992&count=82&index=66;
http://ieeexplore.ieee.org/iel5/8411/26517/01181992.pdf?isnumber=26517&prod=CNF&arnumber=1181992&arSt=+669&ared=+678&arAuthor=Allender%2C+E.%3B+Buhrman%2C+H.%3B+Koucky%2C+M.%3B+van+Melkebeek%2C+D.%3B+Ronneburger%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Roditty:2002:IDR,
author = "L. Roditty and U. Zwick",
title = "Improved dynamic reachability algorithms for directed
graphs",
crossref = "IEEE:2002:PAI",
pages = "679--688",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181993&count=82&index=67;
http://ieeexplore.ieee.org/iel5/8411/26517/01181993.pdf?isnumber=26517&prod=CNF&arnumber=1181993&arSt=+679&ared=+688&arAuthor=Roditty%2C+L.%3B+Zwick%2C+U.",
acknowledgement = ack-nhfb,
}
@InProceedings{Even:2002:CFC,
author = "G. Even and Z. Lotker and D. Ron and S. Smorodinsky",
title = "Conflict-free colorings of simple geometric regions
with applications to frequency assignment in cellular
networks",
crossref = "IEEE:2002:PAI",
pages = "691--700",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181994&count=82&index=68;
http://ieeexplore.ieee.org/iel5/8411/26517/01181994.pdf?isnumber=26517&prod=CNF&arnumber=1181994&arSt=+691&ared=+700&arAuthor=Even%2C+G.%3B+Lotker%2C+Z.%3B+Ron%2C+D.%3B+Smorodinsky%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Benjamini:2002:GIL,
author = "I. Benjamini and L. Lovasz",
title = "Global information from local observation",
crossref = "IEEE:2002:PAI",
pages = "701--710",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181995&count=82&index=69;
http://ieeexplore.ieee.org/iel5/8411/26517/01181995.pdf?isnumber=26517&prod=CNF&arnumber=1181995&arSt=+701&ared=+710&arAuthor=Benjamini%2C+I.%3B+Lovasz%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Cryan:2002:RMM,
author = "M. Cryan and M. Dyer and L. A. Goldberg and M. Jerrum
and R. Martin",
title = "Rapidly mixing {Markov} chains for sampling
contingency tables with a constant number of rows",
crossref = "IEEE:2002:PAI",
pages = "711--720",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181996&count=82&index=70;
http://ieeexplore.ieee.org/iel5/8411/26517/01181996.pdf?isnumber=26517&prod=CNF&arnumber=1181996&arSt=+711&ared=+720&arAuthor=Cryan%2C+M.%3B+Dyer%2C+M.%3B+Goldberg%2C+L.A.%3B+Jerrum%2C+M.%3B+Martin%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Jerrum:2002:SGL,
author = "Mark Jerrum and Jung-Bae Son",
title = "Spectral gap and log-{Sobolev} constant for balanced
matroids",
crossref = "IEEE:2002:PAI",
pages = "721--729",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181997&count=82&index=71;
http://ieeexplore.ieee.org/iel5/8411/26517/01181997.pdf?isnumber=26517&prod=CNF&arnumber=1181997&arSt=+721&ared=+729&arAuthor=Mark+Jerrum%3B+Jung-Bae+Son",
acknowledgement = ack-nhfb,
}
@InProceedings{Ajtai:2002:RLC,
author = "M. Ajtai",
title = "Random lattices and a conjectured $0$-$1$ law about
their polynomial time computable properties",
crossref = "IEEE:2002:PAI",
pages = "733--742",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181998&count=82&index=72;
http://ieeexplore.ieee.org/iel5/8411/26517/01181998.pdf?isnumber=26517&prod=CNF&arnumber=1181998&arSt=+733&ared=+742&arAuthor=Ajtai%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Arvind:2002:GIS,
author = "V. Arvind and P. P. Kurur",
title = "Graph isomorphism is in {SPP}",
crossref = "IEEE:2002:PAI",
pages = "743--750",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1181999&count=82&index=73;
http://ieeexplore.ieee.org/iel5/8411/26517/01181999.pdf?isnumber=26517&prod=CNF&arnumber=1181999&arSt=+743&ared=+750&arAuthor=Arvind%2C+V.%3B+Kurur%2C+P.P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Vereshchagin:2002:KSF,
author = "N. Vereshchagin and P. Vitanyi",
title = "{Kolmogorov}'s structure functions with an application
to the foundations of model selection",
crossref = "IEEE:2002:PAI",
pages = "751--760",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182000&count=82&index=74;
http://ieeexplore.ieee.org/iel5/8411/26517/01182000.pdf?isnumber=26517&prod=CNF&arnumber=1182000&arSt=+751&ared=+760&arAuthor=Vereshchagin%2C+N.%3B+Vitanyi%2C+P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Levin:2002:FI,
author = "L. A. Levin",
title = "Forbidden information",
crossref = "IEEE:2002:PAI",
pages = "761--765",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182001&count=82&index=75;
http://ieeexplore.ieee.org/iel5/8411/26517/01182001.pdf?isnumber=26517&prod=CNF&arnumber=1182001&arSt=+761&ared=+765&arAuthor=Levin%2C+L.A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dubois:2002:XT,
author = "O. Dubois and J. Mandler",
title = "The $3$-{XORSAT} threshold",
crossref = "IEEE:2002:PAI",
pages = "769--778",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182002&count=82&index=76;
http://ieeexplore.ieee.org/iel5/8411/26517/01182002.pdf?isnumber=26517&prod=CNF&arnumber=1182002&arSt=+769&ared=+778&arAuthor=Dubois%2C+O.%3B+Mandler%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Achlioptas:2002:AOR,
author = "D. Achlioptas and C. Moore",
title = "The asymptotic order of the random {$k$-SAT}
threshold",
crossref = "IEEE:2002:PAI",
pages = "779--788",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182003&count=82&index=77;
http://ieeexplore.ieee.org/iel5/8411/26517/01182003.pdf?isnumber=26517&prod=CNF&arnumber=1182003&arSt=+779&ared=+788&arAuthor=Achlioptas%2C+D.%3B+Moore%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Frieze:2002:RST,
author = "A. Frieze",
title = "On random symmetric travelling salesman problems",
crossref = "IEEE:2002:PAI",
pages = "789--798",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182004&count=82&index=78;
http://ieeexplore.ieee.org/iel5/8411/26517/01182004.pdf?isnumber=26517&prod=CNF&arnumber=1182004&arSt=+789&ared=+798&arAuthor=Frieze%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Mitzenmacher:2002:LBM,
author = "M. Mitzenmacher and B. Prabhakar and D. Shah",
title = "Load balancing with memory",
crossref = "IEEE:2002:PAI",
pages = "799--808",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182005&count=82&index=79;
http://ieeexplore.ieee.org/iel5/8411/26517/01182005.pdf?isnumber=26517&prod=CNF&arnumber=1182005&arSt=+799&ared=+808&arAuthor=Mitzenmacher%2C+M.%3B+Prabhakar%2C+B.%3B+Shah%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Hershberger:2002:ESP,
author = "J. Hershberger and Subhash Suri",
title = "Erratum to {``Vickrey pricing and shortest paths: what
is an edge worth?''}",
crossref = "IEEE:2002:PAI",
pages = "809--809",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
note = "See \cite{Hershberger:2001:VPS}.",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182006&count=82&index=80;
http://ieeexplore.ieee.org/iel5/8411/26517/01182006.pdf?isnumber=26517&prod=CNF&arnumber=1182006&arSt=+809&ared=+809&arAuthor=Hershberger%2C+J.%3B+Subhash+Suri",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2002:AI,
author = "Anonymous",
title = "Author index",
crossref = "IEEE:2002:PAI",
pages = "811--813",
year = "2002",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=26517&arnumber=1182007&count=82&index=81;
http://ieeexplore.ieee.org/iel5/8411/26517/01182007.pdf?isnumber=26517&prod=CNF&arnumber=1182007&arSt=+811&ared=+813&arAuthor=",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:2003:MLM,
author = "A. Blum",
title = "Machine learning: my favorite results, directions, and
open problems",
crossref = "IEEE:2003:PAI",
pages = "2--2",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238174&count=66&index=1;
http://ieeexplore.ieee.org/iel5/8767/27770/01238174.pdf?isnumber=27770&prod=CNF&arnumber=1238174&arSt=+2&ared=+2&arAuthor=Blum%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Randall:2003:MMC,
author = "D. Randall",
title = "Mixing [Markov chain]",
crossref = "IEEE:2003:PAI",
pages = "4--15",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238175&count=66&index=2;
http://ieeexplore.ieee.org/iel5/8767/27770/01238175.pdf?isnumber=27770&prod=CNF&arnumber=1238175&arSt=+4&ared=+15&arAuthor=Randall%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Upfal:2003:PAD,
author = "E. Upfal",
title = "Performance analysis of dynamic processes",
crossref = "IEEE:2003:PAI",
pages = "18--18",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238176&count=66&index=3;
http://ieeexplore.ieee.org/iel5/8767/27770/01238176.pdf?isnumber=27770&prod=CNF&arnumber=1238176&arSt=+18&ared=&arAuthor=Upfal%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Cornuejols:2003:PAR,
author = "G. Cornuejols and Xinming Liu and K. Vuskovic",
title = "A polynomial algorithm for recognizing perfect
graphs",
crossref = "IEEE:2003:PAI",
pages = "20--27",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238177&count=66&index=4;
http://ieeexplore.ieee.org/iel5/8767/27770/01238177.pdf?isnumber=27770&prod=CNF&arnumber=1238177&arSt=+20&ared=+27&arAuthor=Cornuejols%2C+G.%3B+Xinming+Liu%3B+Vuskovic%2C+K.",
acknowledgement = ack-nhfb,
}
@InProceedings{Mihail:2003:CCP,
author = "M. Mihail and C. Papadimitriou and A. Saberi",
title = "On certain connectivity properties of the {Internet}
topology",
crossref = "IEEE:2003:PAI",
pages = "28--35",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238178&count=66&index=5;
http://ieeexplore.ieee.org/iel5/8767/27770/01238178.pdf?isnumber=27770&prod=CNF&arnumber=1238178&arSt=+28&ared=+35&arAuthor=Mihail%2C+M.%3B+Papadimitriou%2C+C.%3B+Saberi%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chaudhuri:2003:PTM,
author = "K. Chaudhuri and B. Godfrey and S. Rao and K. Talwar",
title = "Paths, trees, and minimum latency tours",
crossref = "IEEE:2003:PAI",
pages = "36--45",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238179&count=66&index=6;
http://ieeexplore.ieee.org/iel5/8767/27770/01238179.pdf?isnumber=27770&prod=CNF&arnumber=1238179&arSt=+36&ared=+45&arAuthor=Chaudhuri%2C+K.%3B+Godfrey%2C+B.%3B+Rao%2C+S.%3B+Talwar%2C+K.",
acknowledgement = ack-nhfb,
}
@InProceedings{Blum:2003:AAO,
author = "A. Blum and S. Chawla and D. R. Karger and T. Lane and
A. Meyerson and M. Minkoff",
title = "Approximation algorithms for orienteering and
discounted-reward {TSP}",
crossref = "IEEE:2003:PAI",
pages = "46--55",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238180&count=66&index=7;
http://ieeexplore.ieee.org/iel5/8767/27770/01238180.pdf?isnumber=27770&prod=CNF&arnumber=1238180&arSt=+46&ared=+55&arAuthor=Blum%2C+A.%3B+Chawla%2C+S.%3B+Karger%2C+D.R.%3B+Lane%2C+T.%3B+Meyerson%2C+A.%3B+Minkoff%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kaplan:2003:AAA,
author = "H. Kaplan and M. Lewenstein and N. Shafrir and M.
Sviridenko",
title = "Approximation algorithms for asymmetric {TSP} by
decomposing directed regular multigraphs",
crossref = "IEEE:2003:PAI",
pages = "56--65",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238181&count=66&index=8;
http://ieeexplore.ieee.org/iel5/8767/27770/01238181.pdf?isnumber=27770&prod=CNF&arnumber=1238181&arSt=+56&ared=+65&arAuthor=Kaplan%2C+H.%3B+Lewenstein%2C+M.%3B+Shafrir%2C+N.%3B+Sviridenko%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldreich:2003:IHR,
author = "O. Goldreich and S. Goldwasser and A. Nussboim",
title = "On the implementation of huge random objects",
crossref = "IEEE:2003:PAI",
pages = "68--79",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238182&count=66&index=9;
http://ieeexplore.ieee.org/iel5/8767/27770/01238182.pdf?isnumber=27770&prod=CNF&arnumber=1238182&arSt=+68&ared=+79&arAuthor=Goldreich%2C+O.%3B+Goldwasser%2C+S.%3B+Nussboim%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Micali:2003:ZKS,
author = "S. Micali and M. Rabin and J. Kilian",
title = "Zero-knowledge sets",
crossref = "IEEE:2003:PAI",
pages = "80--91",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238183&count=66&index=10;
http://ieeexplore.ieee.org/iel5/8767/27770/01238183.pdf?isnumber=27770&prod=CNF&arnumber=1238183&arSt=+80&ared=+91&arAuthor=Micali%2C+S.%3B+Rabin%2C+M.%3B+Kilian%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kamp:2003:DEB,
author = "J. Kamp and D. Zuckerman",
title = "Deterministic extractors for bit-fixing sources and
exposure-resilient cryptography",
crossref = "IEEE:2003:PAI",
pages = "92--101",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238184&count=66&index=11;
http://ieeexplore.ieee.org/iel5/8767/27770/01238184.pdf?isnumber=27770&prod=CNF&arnumber=1238184&arSt=+92&ared=+101&arAuthor=Kamp%2C+J.%3B+Zuckerman%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldwasser:2003:SFS,
author = "S. Goldwasser and Y. T. Kalai",
title = "On the (In)security of the {Fiat--Shamir} paradigm",
crossref = "IEEE:2003:PAI",
pages = "102--113",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238185&count=66&index=12;
http://ieeexplore.ieee.org/iel5/8767/27770/01238185.pdf?isnumber=27770&prod=CNF&arnumber=1238185&arSt=+102&ared=+113&arAuthor=Goldwasser%2C+S.%3B+Kalai%2C+Y.T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Babai:2003:LTC,
author = "L. Babai and A. Shpilka and D. Stefankovic",
title = "Locally testable cyclic codes",
crossref = "IEEE:2003:PAI",
pages = "116--125",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238186&count=66&index=13;
http://ieeexplore.ieee.org/iel5/8767/27770/01238186.pdf?isnumber=27770&prod=CNF&arnumber=1238186&arSt=+116&ared=+125&arAuthor=Babai%2C+L.%3B+Shpilka%2C+A.%3B+Stefankovic%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Trevisan:2003:LDU,
author = "L. Trevisan",
title = "List-decoding using the {XOR} lemma",
crossref = "IEEE:2003:PAI",
pages = "126--135",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238187&count=66&index=14;
http://ieeexplore.ieee.org/iel5/8767/27770/01238187.pdf?isnumber=27770&prod=CNF&arnumber=1238187&arSt=+126&ared=+135&arAuthor=Trevisan%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Mossel:2003:SEB,
author = "E. Mossel and A. Shpilka and L. Trevisan",
title = "On $\epsilon$-biased generators in {NC}$^0$",
crossref = "IEEE:2003:PAI",
pages = "136--145",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238188&count=66&index=15;
http://ieeexplore.ieee.org/iel5/8767/27770/01238188.pdf?isnumber=27770&prod=CNF&arnumber=1238188&arSt=+136&ared=+145&arAuthor=Mossel%2C+E.%3B+Shpilka%2C+A.%3B+Trevisan%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Akavia:2003:PHC,
author = "A. Akavia and S. Goldwasser and S. Safra",
title = "Proving hard-core predicates using list decoding",
crossref = "IEEE:2003:PAI",
pages = "146--157",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238189&count=66&index=16;
http://ieeexplore.ieee.org/iel5/8767/27770/01238189.pdf?isnumber=27770&prod=CNF&arnumber=1238189&arSt=+146&ared=+157&arAuthor=Akavia%2C+A.%3B+Goldwasser%2C+S.%3B+Safra%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bhattacharjee:2003:IFA,
author = "R. Bhattacharjee and A. Goel",
title = "Instability of {FIFO} at arbitrarily low rates in the
adversarial queuing model",
crossref = "IEEE:2003:PAI",
pages = "160--167",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238190&count=66&index=17;
http://ieeexplore.ieee.org/iel5/8767/27770/01238190.pdf?isnumber=27770&prod=CNF&arnumber=1238190&arSt=+160&ared=+167&arAuthor=Bhattacharjee%2C+R.%3B+Goel%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Nair:2003:PPC,
author = "C. Nair and B. Prabhakar and M. Sharma",
title = "Proofs of the {Parisi} and {Coppersmith--Sorkin}
conjectures for the finite random assignment problem",
crossref = "IEEE:2003:PAI",
pages = "168--178",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238191&count=66&index=18;
http://ieeexplore.ieee.org/iel5/8767/27770/01238191.pdf?isnumber=27770&prod=CNF&arnumber=1238191&arSt=+168&ared=+178&arAuthor=Nair%2C+C.%3B+Prabhakar%2C+B.%3B+Sharma%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Orlitsky:2003:AGT,
author = "A. Orlitsky and N. P. Santhanam and J. Zhang",
title = "{Always Good Turing:} asymptotically optimal
probability estimation",
crossref = "IEEE:2003:PAI",
pages = "179--188",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238192&count=66&index=19;
http://ieeexplore.ieee.org/iel5/8767/27770/01238192.pdf?isnumber=27770&prod=CNF&arnumber=1238192&arSt=+179&ared=+188&arAuthor=Orlitsky%2C+A.%3B+Santhanam%2C+N.P.%3B+Zhang%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bshouty:2003:LDR,
author = "N. Bshouty and E. Mossel and R. O'Donnell and R. A.
Servedio",
title = "Learning {DNF} from random walks",
crossref = "IEEE:2003:PAI",
pages = "189--198",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238193&count=66&index=20;
http://ieeexplore.ieee.org/iel5/8767/27770/01238193.pdf?isnumber=27770&prod=CNF&arnumber=1238193&arSt=+189&ared=+198&arAuthor=Bshouty%2C+N.%3B+Mossel%2C+E.%3B+O%27Donnell%2C+R.%3B+Servedio%2C+R.A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Aaronson:2003:QSS,
author = "S. Aaronson and A. Ambainis",
title = "Quantum search of spatial regions",
crossref = "IEEE:2003:PAI",
pages = "200--209",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238194&count=66&index=21;
http://ieeexplore.ieee.org/iel5/8767/27770/01238194.pdf?isnumber=27770&prod=CNF&arnumber=1238194&arSt=+200&ared=+209&arAuthor=Aaronson%2C+S.%3B+Ambainis%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Aharonov:2003:LPQ,
author = "D. Aharonov and O. Regev",
title = "A lattice problem in quantum {NP}",
crossref = "IEEE:2003:PAI",
pages = "210--219",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238195&count=66&index=22;
http://ieeexplore.ieee.org/iel5/8767/27770/01238195.pdf?isnumber=27770&prod=CNF&arnumber=1238195&arSt=+210&ared=+219&arAuthor=Aharonov%2C+D.%3B+Regev%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Jain:2003:LBB,
author = "R. Jain and J. Radhakrishnan and Sen P",
title = "A lower bound for the bounded round quantum
communication complexity of set disjointness",
crossref = "IEEE:2003:PAI",
pages = "220--229",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238196&count=66&index=23;
http://ieeexplore.ieee.org/iel5/8767/27770/01238196.pdf?isnumber=27770&prod=CNF&arnumber=1238196&arSt=+220&ared=+229&arAuthor=Jain%2C+R.%3B+Radhakrishnan%2C+J.%3B+Sen+P",
acknowledgement = ack-nhfb,
}
@InProceedings{Ambainis:2003:PDV,
author = "A. Ambainis",
title = "Polynomial degree vs. quantum query complexity",
crossref = "IEEE:2003:PAI",
pages = "230--239",
year = "2003",
bibdate = "Fri Jul 15 16:13:02 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238197&count=66&index=24;
http://ieeexplore.ieee.org/iel5/8767/27770/01238197.pdf?isnumber=27770&prod=CNF&arnumber=1238197&arSt=+230&ared=+239&arAuthor=Ambainis%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Franceschini:2003:PSC,
author = "G. Franceschini and V. Geffert",
title = "An in-place sorting with {$O(n \log n)$} comparisons
and {$O(n)$} moves",
crossref = "IEEE:2003:PAI",
pages = "242--250",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238198&count=66&index=25;
http://ieeexplore.ieee.org/iel5/8767/27770/01238198.pdf?isnumber=27770&prod=CNF&arnumber=1238198&arSt=+242&ared=+250&arAuthor=Franceschini%2C+G.%3B+Geffert%2C+V.",
acknowledgement = ack-nhfb,
}
@InProceedings{Hon:2003:BTS,
author = "Wing-Kai Hon and K. Sadakane and Wing-Kin Sung",
title = "Breaking a time-and-space barrier in constructing
full-text indices",
crossref = "IEEE:2003:PAI",
pages = "251--260",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238199&count=66&index=26;
http://ieeexplore.ieee.org/iel5/8767/27770/01238199.pdf?isnumber=27770&prod=CNF&arnumber=1238199&arSt=+251&ared=+260&arAuthor=Wing-Kai+Hon%3B+Sadakane%2C+K.%3B+Wing-Kin+Sung",
acknowledgement = ack-nhfb,
}
@InProceedings{Arge:2003:ESC,
author = "L. Arge and N. Zeh",
title = "{I/O}-efficient strong connectivity and depth-first
search for directed planar graphs",
crossref = "IEEE:2003:PAI",
pages = "261--270",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238200&count=66&index=27;
http://ieeexplore.ieee.org/iel5/8767/27770/01238200.pdf?isnumber=27770&prod=CNF&arnumber=1238200&arSt=+261&ared=+270&arAuthor=Arge%2C+L.%3B+Zeh%2C+N.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bender:2003:CCO,
author = "M. A. Bender and G. S. Brodal and R. Fagerberg and D.
Ge and Simai He and Haodung Hu and J. Iacono and A.
Lopez-Ortiz",
title = "The cost of cache-oblivious searching",
crossref = "IEEE:2003:PAI",
pages = "271--282",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238201&count=66&index=28;
http://ieeexplore.ieee.org/iel5/8767/27770/01238201.pdf?isnumber=27770&prod=CNF&arnumber=1238201&arSt=+271&ared=+282&arAuthor=Bender%2C+M.A.%3B+Brodal%2C+G.S.%3B+Fagerberg%2C+R.%3B+Ge%2C+D.%3B+Simai+He%3B+Haodung+Hu%3B+Iacono%2C+J.%3B+Lopez-Ortiz%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Indyk:2003:TLB,
author = "P. Indyk and D. Woodruff",
title = "Tight lower bounds for the distinct elements problem",
crossref = "IEEE:2003:PAI",
pages = "283--288",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238202&count=66&index=29;
http://ieeexplore.ieee.org/iel5/8767/27770/01238202.pdf?isnumber=27770&prod=CNF&arnumber=1238202&arSt=+283&ared=+288&arAuthor=Indyk%2C+P.%3B+Woodruff%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Khot:2003:HAS,
author = "S. Khot",
title = "Hardness of approximating the shortest vector problem
in high {$L_p$} norms",
crossref = "IEEE:2003:PAI",
pages = "290--297",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238203&count=66&index=30;
http://ieeexplore.ieee.org/iel5/8767/27770/01238203.pdf?isnumber=27770&prod=CNF&arnumber=1238203&arSt=+290&ared=+297&arAuthor=Khot%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2003:MAC,
author = "M. Alekhnovich",
title = "More on average case vs approximation complexity",
crossref = "IEEE:2003:PAI",
pages = "298--307",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238204&count=66&index=31;
http://ieeexplore.ieee.org/iel5/8767/27770/01238204.pdf?isnumber=27770&prod=CNF&arnumber=1238204&arSt=+298&ared=+307&arAuthor=Alekhnovich%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bogdanov:2003:WCA,
author = "A. Bogdanov and L. Trevisan",
title = "On worst-case to average-case reductions for {NP}
problems",
crossref = "IEEE:2003:PAI",
pages = "308--317",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238205&count=66&index=32;
http://ieeexplore.ieee.org/iel5/8767/27770/01238205.pdf?isnumber=27770&prod=CNF&arnumber=1238205&arSt=+308&ared=+317&arAuthor=Bogdanov%2C+A.%3B+Trevisan%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Buresh-Oppenheim:2003:RBI,
author = "J. Buresh-Oppenheim and N. Galesi and S. Hoory and A.
Magen and T. Pitassi",
title = "Rank bounds and integrality gaps for cutting planes
procedures",
crossref = "IEEE:2003:PAI",
pages = "318--327",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238206&count=66&index=33;
http://ieeexplore.ieee.org/iel5/8767/27770/01238206.pdf?isnumber=27770&prod=CNF&arnumber=1238206&arSt=+318&ared=+327&arAuthor=Buresh-Oppenheim%2C+J.%3B+Galesi%2C+N.%3B+Hoory%2C+S.%3B+Magen%2C+A.%3B+Pitassi%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Molloy:2003:RCR,
author = "M. Molloy and M. Salavatipour",
title = "The resolution complexity of random constraint
satisfaction problems",
crossref = "IEEE:2003:PAI",
pages = "330--339",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238207&count=66&index=34;
http://ieeexplore.ieee.org/iel5/8767/27770/01238207.pdf?isnumber=27770&prod=CNF&arnumber=1238207&arSt=+330&ared=+339&arAuthor=Molloy%2C+M.%3B+Salavatipour%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bacchus:2003:ACR,
author = "F. Bacchus and S. Dalmao and T. Pitassi",
title = "Algorithms and complexity results for {\#SAT} and
{Bayesian} inference",
crossref = "IEEE:2003:PAI",
pages = "340--351",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238208&count=66&index=35;
http://ieeexplore.ieee.org/iel5/8767/27770/01238208.pdf?isnumber=27770&prod=CNF&arnumber=1238208&arSt=+340&ared=+351&arAuthor=Bacchus%2C+F.%3B+Dalmao%2C+S.%3B+Pitassi%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2003:LUB,
author = "M. Alekhnovich and E. Ben-Sasson",
title = "Linear upper bounds for random walk on small density
random {$3$-CNFs}",
crossref = "IEEE:2003:PAI",
pages = "352--361",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238209&count=66&index=36;
http://ieeexplore.ieee.org/iel5/8767/27770/01238209.pdf?isnumber=27770&prod=CNF&arnumber=1238209&arSt=+352&ared=+361&arAuthor=Alekhnovich%2C+M.%3B+Ben-Sasson%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Achlioptas:2003:MSR,
author = "D. Achlioptas and A. Naor and Y. Peres",
title = "On the maximum satisfiability of random formulas",
crossref = "IEEE:2003:PAI",
pages = "362--370",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238210&count=66&index=37;
http://ieeexplore.ieee.org/iel5/8767/27770/01238210.pdf?isnumber=27770&prod=CNF&arnumber=1238210&arSt=+362&ared=+370&arAuthor=Achlioptas%2C+D.%3B+Naor%2C+A.%3B+Peres%2C+Y.",
acknowledgement = ack-nhfb,
}
@InProceedings{Impagliazzo:2003:LRA,
author = "R. Impagliazzo and B. M. Kapron",
title = "Logics for reasoning about cryptographic
constructions",
crossref = "IEEE:2003:PAI",
pages = "372--383",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238211&count=66&index=38;
http://ieeexplore.ieee.org/iel5/8767/27770/01238211.pdf?isnumber=27770&prod=CNF&arnumber=1238211&arSt=+372&ared=+383&arAuthor=Impagliazzo%2C+R.%3B+Kapron%2C+B.M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2003:LBN,
author = "B. Barak and Y. Lindell and S. Vadhan",
title = "Lower bounds for non-black-box zero knowledge",
crossref = "IEEE:2003:PAI",
pages = "384--393",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238212&count=66&index=39;
http://ieeexplore.ieee.org/iel5/8767/27770/01238212.pdf?isnumber=27770&prod=CNF&arnumber=1238212&arSt=+384&ared=+393&arAuthor=Barak%2C+B.%3B+Lindell%2C+Y.%3B+Vadhan%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Lindell:2003:GCU,
author = "Y. Lindell",
title = "General composition and universal composability in
secure multi-party computation",
crossref = "IEEE:2003:PAI",
pages = "394--403",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238213&count=66&index=40;
http://ieeexplore.ieee.org/iel5/8767/27770/01238213.pdf?isnumber=27770&prod=CNF&arnumber=1238213&arSt=+394&ared=+403&arAuthor=Lindell%2C+Y.",
acknowledgement = ack-nhfb,
}
@InProceedings{Pass:2003:BCS,
author = "R. Pass and A. Rosen",
title = "Bounded-concurrent secure two-party computation in a
constant number of rounds",
crossref = "IEEE:2003:PAI",
pages = "404--413",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238214&count=66&index=41;
http://ieeexplore.ieee.org/iel5/8767/27770/01238214.pdf?isnumber=27770&prod=CNF&arnumber=1238214&arSt=+404&ared=+413&arAuthor=Pass%2C+R.%3B+Rosen%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Spielman:2003:SSS,
author = "D. A. Spielman and Shang-Hua Teng",
title = "Solving sparse, symmetric, diagonally-dominant linear
systems in time {$O(m^{1.31})$}",
crossref = "IEEE:2003:PAI",
pages = "416--427",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238215&count=66&index=42;
http://ieeexplore.ieee.org/iel5/8767/27770/01238215.pdf?isnumber=27770&prod=CNF&arnumber=1238215&arSt=+416&ared=+427&arAuthor=Spielman%2C+D.A.%3B+Shang-Hua+Teng",
acknowledgement = ack-nhfb,
}
@InProceedings{Beimel:2003:SPM,
author = "A. Beimel and E. Weinreb",
title = "Separating the power of monotone span programs over
different fields",
crossref = "IEEE:2003:PAI",
pages = "428--501",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238216&count=66&index=43;
http://ieeexplore.ieee.org/iel5/8767/27770/01238216.pdf?isnumber=27770&prod=CNF&arnumber=1238216&arSt=+428&ared=+501&arAuthor=Beimel%2C+A.%3B+Weinreb%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Cohn:2003:GTA,
author = "H. Cohn and C. Umans",
title = "A group-theoretic approach to fast matrix
multiplication",
crossref = "IEEE:2003:PAI",
pages = "438--449",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238217&count=66&index=44;
http://ieeexplore.ieee.org/iel5/8767/27770/01238217.pdf?isnumber=27770&prod=CNF&arnumber=1238217&arSt=+438&ared=+449&arAuthor=Cohn%2C+H.%3B+Umans%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bhatnagar:2003:SPZ,
author = "N. Bhatnagar and P. Gopalan and R. J. Lipton",
title = "Symmetric polynomials over {$\mathbb{Z}_m$} and
simultaneous communication protocols",
crossref = "IEEE:2003:PAI",
pages = "450--459",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238218&count=66&index=45;
http://ieeexplore.ieee.org/iel5/8767/27770/01238218.pdf?isnumber=27770&prod=CNF&arnumber=1238218&arSt=+450&ared=+459&arAuthor=Bhatnagar%2C+N.%3B+Gopalan%2C+P.%3B+Lipton%2C+R.J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Becchetti:2003:ACS,
author = "L. Becchetti and S. Leonardi and A.
Marchetti-Spaccamela and G. Schafer and T. Vredeveld",
title = "Average case and smoothed competitive analysis of the
multi-level feedback algorithm",
crossref = "IEEE:2003:PAI",
pages = "462--471",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238219&count=66&index=46;
http://ieeexplore.ieee.org/iel5/8767/27770/01238219.pdf?isnumber=27770&prod=CNF&arnumber=1238219&arSt=+462&ared=+471&arAuthor=Becchetti%2C+L.%3B+Leonardi%2C+S.%3B+Marchetti-Spaccamela%2C+A.%3B+Schafer%2C+G.%3B+Vredeveld%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Anagnostopoulos:2003:SER,
author = "A. Anagnostopoulos and A. Kirsch and E. Upfal",
title = "Stability and efficiency of a random local load
balancing protocol",
crossref = "IEEE:2003:PAI",
pages = "472--481",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238220&count=66&index=47;
http://ieeexplore.ieee.org/iel5/8767/27770/01238220.pdf?isnumber=27770&prod=CNF&arnumber=1238220&arSt=+472&ared=+481&arAuthor=Anagnostopoulos%2C+A.%3B+Kirsch%2C+A.%3B+Upfal%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kempe:2003:GBC,
author = "D. Kempe and A. Dobra and J. Gehrke",
title = "Gossip-based computation of aggregate information",
crossref = "IEEE:2003:PAI",
pages = "482--491",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238221&count=66&index=48;
http://ieeexplore.ieee.org/iel5/8767/27770/01238221.pdf?isnumber=27770&prod=CNF&arnumber=1238221&arSt=+482&ared=+491&arAuthor=Kempe%2C+D.%3B+Dobra%2C+A.%3B+Gehrke%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Czumaj:2003:BAR,
author = "A. Czumaj and W. Rytter",
title = "Broadcasting algorithms in radio networks with unknown
topology",
crossref = "IEEE:2003:PAI",
pages = "492--501",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238222&count=66&index=49;
http://ieeexplore.ieee.org/iel5/8767/27770/01238222.pdf?isnumber=27770&prod=CNF&arnumber=1238222&arSt=+492&ared=+501&arAuthor=Czumaj%2C+A.%3B+Rytter%2C+W.",
acknowledgement = ack-nhfb,
}
@InProceedings{Aggarwal:2003:SSR,
author = "G. Aggarwal and R. Motwani and D. Shah and An Zhu",
title = "Switch scheduling via randomized edge coloring",
crossref = "IEEE:2003:PAI",
pages = "502--512",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238223&count=66&index=50;
http://ieeexplore.ieee.org/iel5/8767/27770/01238223.pdf?isnumber=27770&prod=CNF&arnumber=1238223&arSt=+502&ared=+512&arAuthor=Aggarwal%2C+G.%3B+Motwani%2C+R.%3B+Shah%2C+D.%3B+An+Zhu",
acknowledgement = ack-nhfb,
}
@InProceedings{Brinkman:2003:IDR,
author = "B. Brinkman and M. Charikar",
title = "On the impossibility of dimension reduction in
$\ell_1$",
crossref = "IEEE:2003:PAI",
pages = "514--523",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238224&count=66&index=51;
http://ieeexplore.ieee.org/iel5/8767/27770/01238224.pdf?isnumber=27770&prod=CNF&arnumber=1238224&arSt=+514&ared=+523&arAuthor=Brinkman%2C+B.%3B+Charikar%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Charikar:2003:CQI,
author = "M. Charikar and V. Guruswami and A. Wirth",
title = "Clustering with qualitative information",
crossref = "IEEE:2003:PAI",
pages = "524--533",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238225&count=66&index=52;
http://ieeexplore.ieee.org/iel5/8767/27770/01238225.pdf?isnumber=27770&prod=CNF&arnumber=1238225&arSt=+524&ared=+533&arAuthor=Charikar%2C+M.%3B+Guruswami%2C+V.%3B+Wirth%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2003:BGF,
author = "A. Gupta and R. Krauthgamer and J. R. Lee",
title = "Bounded geometries, fractals, and low-distortion
embeddings",
crossref = "IEEE:2003:PAI",
pages = "534--543",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238226&count=66&index=53;
http://ieeexplore.ieee.org/iel5/8767/27770/01238226.pdf?isnumber=27770&prod=CNF&arnumber=1238226&arSt=+534&ared=+543&arAuthor=Gupta%2C+A.%3B+Krauthgamer%2C+R.%3B+Lee%2C+J.R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chan:2003:LAC,
author = "T. M. Chan",
title = "On levels in arrangements of curves. {II}. {A} simple
inequality and its consequences",
crossref = "IEEE:2003:PAI",
pages = "544--550",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238227&count=66&index=54;
http://ieeexplore.ieee.org/iel5/8767/27770/01238227.pdf?isnumber=27770&prod=CNF&arnumber=1238227&arSt=+544&ared=+550&arAuthor=Chan%2C+T.M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Grohe:2003:CHC,
author = "M. Grohe",
title = "The complexity of homomorphism and constraint
satisfaction problems seen from the other side",
crossref = "IEEE:2003:PAI",
pages = "552--561",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238228&count=66&index=55;
http://ieeexplore.ieee.org/iel5/8767/27770/01238228.pdf?isnumber=27770&prod=CNF&arnumber=1238228&arSt=+552&ared=+561&arAuthor=Grohe%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bulatov:2003:TDT,
author = "A. A. Bulatov and V. Dalmau",
title = "Towards a dichotomy theorem for the counting
constraint satisfaction problem",
crossref = "IEEE:2003:PAI",
pages = "562--571",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238229&count=66&index=56;
http://ieeexplore.ieee.org/iel5/8767/27770/01238229.pdf?isnumber=27770&prod=CNF&arnumber=1238229&arSt=+562&ared=+571&arAuthor=Bulatov%2C+A.A.%3B+Dalmau%2C+V.",
acknowledgement = ack-nhfb,
}
@InProceedings{Lavi:2003:TCT,
author = "R. Lavi and Ahuva Mu'alem and N. Nisan",
title = "Towards a characterization of truthful combinatorial
auctions",
crossref = "IEEE:2003:PAI",
pages = "574--583",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238230&count=66&index=57;
http://ieeexplore.ieee.org/iel5/8767/27770/01238230.pdf?isnumber=27770&prod=CNF&arnumber=1238230&arSt=+574&ared=+583&arAuthor=Lavi%2C+R.%3B+Ahuva+Mu%27alem%3B+Nisan%2C+N.",
acknowledgement = ack-nhfb,
}
@InProceedings{Pal:2003:GSP,
author = "M. Pal and E. Tardos",
title = "Group strategy proof mechanisms via primal-dual
algorithms",
crossref = "IEEE:2003:PAI",
pages = "584--593",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238231&count=66&index=58;
http://ieeexplore.ieee.org/iel5/8767/27770/01238231.pdf?isnumber=27770&prod=CNF&arnumber=1238231&arSt=+584&ared=+593&arAuthor=Pal%2C+M.%3B+Tardos%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kleinberg:2003:VKD,
author = "R. Kleinberg and T. Leighton",
title = "The value of knowing a demand curve: bounds on regret
for online posted-price auctions",
crossref = "IEEE:2003:PAI",
pages = "594--605",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238232&count=66&index=59;
http://ieeexplore.ieee.org/iel5/8767/27770/01238232.pdf?isnumber=27770&prod=CNF&arnumber=1238232&arSt=+594&ared=+605&arAuthor=Kleinberg%2C+R.%3B+Leighton%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2003:ACS,
author = "A. Gupta and A. Kumar and M. Pal and T. Roughgarden",
title = "Approximation via cost-sharing: a simple approximation
algorithm for the multicommodity rent-or-buy problem",
crossref = "IEEE:2003:PAI",
pages = "606--615",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238233&count=66&index=60;
http://ieeexplore.ieee.org/iel5/8767/27770/01238233.pdf?isnumber=27770&prod=CNF&arnumber=1238233&arSt=+606&ared=+615&arAuthor=Gupta%2C+A.%3B+Kumar%2C+A.%3B+Pal%2C+M.%3B+Roughgarden%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Hayes:2003:NMC,
author = "T. P. Hayes and E. Vigoda",
title = "A non-{Markovian} coupling for randomly sampling
colorings",
crossref = "IEEE:2003:PAI",
pages = "618--627",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238234&count=66&index=61;
http://ieeexplore.ieee.org/iel5/8767/27770/01238234.pdf?isnumber=27770&prod=CNF&arnumber=1238234&arSt=+618&ared=+627&arAuthor=Hayes%2C+T.P.%3B+Vigoda%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Martinelli:2003:IMT,
author = "F. Martinelli and A. Sinclair and D. Weitz",
title = "The {Ising} model on trees: boundary conditions and
mixing time",
crossref = "IEEE:2003:PAI",
pages = "628--639",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238235&count=66&index=62;
http://ieeexplore.ieee.org/iel5/8767/27770/01238235.pdf?isnumber=27770&prod=CNF&arnumber=1238235&arSt=+628&ared=+639&arAuthor=Martinelli%2C+F.%3B+Sinclair%2C+A.%3B+Weitz%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Lovasz:2003:LFG,
author = "L. Lovasz and S. Vempala",
title = "Logconcave functions: geometry and efficient sampling
algorithms",
crossref = "IEEE:2003:PAI",
pages = "640--649",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238236&count=66&index=63;
http://ieeexplore.ieee.org/iel5/8767/27770/01238236.pdf?isnumber=27770&prod=CNF&arnumber=1238236&arSt=+640&ared=+649&arAuthor=Lovasz%2C+L.%3B+Vempala%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Lovasz:2003:SAC,
author = "L. Lovasz and S. Vempala",
title = "Simulated annealing in convex bodies and an
{$O*(n^4)$} volume algorithm",
crossref = "IEEE:2003:PAI",
pages = "650--659",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238237&count=66&index=64;
http://ieeexplore.ieee.org/iel5/8767/27770/01238237.pdf?isnumber=27770&prod=CNF&arnumber=1238237&arSt=+650&ared=+659&arAuthor=Lovasz%2C+L.%3B+Vempala%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Anonymous:2003:AI,
author = "Anonymous",
title = "Author Index",
crossref = "IEEE:2003:PAI",
pages = "660--661",
year = "2003",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=27770&arnumber=1238238&count=66&index=65;
http://ieeexplore.ieee.org/iel5/8767/27770/01238238.pdf?isnumber=27770&prod=CNF&arnumber=1238238&arSt=+660&ared=+661&arAuthor=",
acknowledgement = ack-nhfb,
}
@InProceedings{Mochon:2004:QWC,
author = "C. Mochon",
title = "Quantum weak coin-flipping with bias of 0.192",
crossref = "IEEE:2004:PAI",
pages = "2--11",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366219&count=64&index=0;
http://ieeexplore.ieee.org/iel5/9430/29918/01366219.pdf?isnumber=29918&prod=CNF&arnumber=1366219&arSt=+2&ared=+11&arAuthor=Mochon%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Klauck:2004:QCS,
author = "H. Klauck and R. Spalek and R. de Wolf",
title = "Quantum and classical strong direct product theorems
and optimal time-space tradeoffs",
crossref = "IEEE:2004:PAI",
pages = "12--21",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366220&count=64&index=1;
http://ieeexplore.ieee.org/iel5/9430/29918/01366220.pdf?isnumber=29918&prod=CNF&arnumber=1366220&arSt=+12&ared=+21&arAuthor=Klauck%2C+H.%3B+Spalek%2C+R.%3B+de+Wolf%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Ambainis:2004:QWA,
author = "A. Ambainis",
title = "Quantum walk algorithm for element distinctness",
crossref = "IEEE:2004:PAI",
pages = "22--31",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366221&count=64&index=2;
http://ieeexplore.ieee.org/iel5/9430/29918/01366221.pdf?isnumber=29918&prod=CNF&arnumber=1366221&arSt=+22&ared=+31&arAuthor=Ambainis%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Szegedy:2004:QSM,
author = "M. Szegedy",
title = "Quantum speed-up of {Markov} chain based algorithms",
crossref = "IEEE:2004:PAI",
pages = "32--41",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366222&count=64&index=3;
http://ieeexplore.ieee.org/iel5/9430/29918/01366222.pdf?isnumber=29918&prod=CNF&arnumber=1366222&arSt=+32&ared=+41&arAuthor=Szegedy%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Aharonov:2004:AQC,
author = "D. Aharonov and W. van Dam and J. Kempe and Z. Landau
and S. Lloyd and O. Regev",
title = "Adiabatic quantum computation is equivalent to
standard quantum computation",
crossref = "IEEE:2004:PAI",
pages = "42--51",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366223&count=64&index=4;
http://ieeexplore.ieee.org/iel5/9430/29918/01366223.pdf?isnumber=29918&prod=CNF&arnumber=1366223&arSt=+42&ared=+51&arAuthor=Aharonov%2C+D.%3B+van+Dam%2C+W.%3B+Kempe%2C+J.%3B+Landau%2C+Z.%3B+Lloyd%2C+S.%3B+Regev%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Charikar:2004:MQP,
author = "M. Charikar and A. Wirth",
title = "Maximizing quadratic programs: extending
{Grothendieck}'s inequality",
crossref = "IEEE:2004:PAI",
pages = "54--60",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366224&count=64&index=5;
http://ieeexplore.ieee.org/iel5/9430/29918/01366224.pdf?isnumber=29918&prod=CNF&arnumber=1366224&arSt=+54&ared=+60&arAuthor=Charikar%2C+M.%3B+Wirth%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Lau:2004:AMS,
author = "Lap Chi Lau",
title = "An approximate max-{Steiner}-tree-packing
min-{Steiner}-cut theorem",
crossref = "IEEE:2004:PAI",
pages = "61--70",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366225&count=64&index=6;
http://ieeexplore.ieee.org/iel5/9430/29918/01366225.pdf?isnumber=29918&prod=CNF&arnumber=1366225&arSt=+61&ared=+70&arAuthor=Lap+Chi+Lau",
acknowledgement = ack-nhfb,
}
@InProceedings{Chekuri:2004:EDP,
author = "C. Chekuri and S. Khanna and F. B. Shepherd",
title = "Edge-disjoint paths in planar graphs",
crossref = "IEEE:2004:PAI",
pages = "71--80",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366226&count=64&index=7;
http://ieeexplore.ieee.org/iel5/9430/29918/01366226.pdf?isnumber=29918&prod=CNF&arnumber=1366226&arSt=+71&ared=+80&arAuthor=Chekuri%2C+C.%3B+Khanna%2C+S.%3B+Shepherd%2C+F.B.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chuzhoy:2004:MMS,
author = "J. Chuzhoy and S. Guha and S. Khanna and J. S. Naor",
title = "Machine minimization for scheduling jobs with interval
constraints",
crossref = "IEEE:2004:PAI",
pages = "81--90",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366227&count=64&index=8;
http://ieeexplore.ieee.org/iel5/9430/29918/01366227.pdf?isnumber=29918&prod=CNF&arnumber=1366227&arSt=+81&ared=+90&arAuthor=Chuzhoy%2C+J.%3B+Guha%2C+S.%3B+Khanna%2C+S.%3B+Naor%2C+J.S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Matousek:2004:REC,
author = "J. Matousek and T. Szabo",
title = "Random edge can be exponential on abstract cubes",
crossref = "IEEE:2004:PAI",
pages = "92--100",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366228&count=64&index=9;
http://ieeexplore.ieee.org/iel5/9430/29918/01366228.pdf?isnumber=29918&prod=CNF&arnumber=1366228&arSt=+92&ared=+100&arAuthor=Matousek%2C+J.%3B+Szabo%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Charikar:2004:IRA,
author = "M. Charikar and M. X. Goemans and H. Karloff",
title = "On the integrality ratio for asymmetric {TSP}",
crossref = "IEEE:2004:PAI",
pages = "101--107",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366229&count=64&index=10;
http://ieeexplore.ieee.org/iel5/9430/29918/01366229.pdf?isnumber=29918&prod=CNF&arnumber=1366229&arSt=+101&ared=+107&arAuthor=Charikar%2C+M.%3B+Goemans%2C+M.X.%3B+Karloff%2C+H.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chuzhoy:2004:HML,
author = "J. Chuzhoy and J. S. Naor",
title = "The hardness of metric labeling",
crossref = "IEEE:2004:PAI",
pages = "108--114",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366230&count=64&index=11;
http://ieeexplore.ieee.org/iel5/9430/29918/01366230.pdf?isnumber=29918&prod=CNF&arnumber=1366230&arSt=+108&ared=+114&arAuthor=Chuzhoy%2C+J.%3B+Naor%2C+J.S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Andrews:2004:HBB,
author = "M. Andrews",
title = "Hardness of buy-at-bulk network design",
crossref = "IEEE:2004:PAI",
pages = "115--124",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366231&count=64&index=12;
http://ieeexplore.ieee.org/iel5/9430/29918/01366231.pdf?isnumber=29918&prod=CNF&arnumber=1366231&arSt=+115&ared=+124&arAuthor=Andrews%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Khot:2004:HAS,
author = "S. Khot",
title = "Hardness of approximating the shortest vector problem
in lattices",
crossref = "IEEE:2004:PAI",
pages = "126--135",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366232&count=64&index=13;
http://ieeexplore.ieee.org/iel5/9430/29918/01366232.pdf?isnumber=29918&prod=CNF&arnumber=1366232&arSt=+126&ared=+135&arAuthor=Khot%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Khot:2004:RPG,
author = "S. Khot",
title = "Ruling out {PTAS} for graph min-bisection, densest
subgraph and bipartite clique",
crossref = "IEEE:2004:PAI",
pages = "136--145",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366233&count=64&index=14;
http://ieeexplore.ieee.org/iel5/9430/29918/01366233.pdf?isnumber=29918&prod=CNF&arnumber=1366233&arSt=+136&ared=+145&arAuthor=Khot%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Khot:2004:OIR,
author = "S. Khot and G. Kindler and E. Mossel and R.
O'Donnell",
title = "Optimal inapproximability results for {MAX-CUT} and
other $2$-variable {CSPs}?",
crossref = "IEEE:2004:PAI",
pages = "146--154",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366234&count=64&index=15;
http://ieeexplore.ieee.org/iel5/9430/29918/01366234.pdf?isnumber=29918&prod=CNF&arnumber=1366234&arSt=+146&ared=+154&arAuthor=Khot%2C+S.%3B+Kindler%2C+G.%3B+Mossel%2C+E.%3B+O%27Donnell%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dinur:2004:ATT,
author = "I. Dinur and O. Reingold",
title = "Assignment testers: towards a combinatorial proof of
the {PCP}-theorem",
crossref = "IEEE:2004:PAI",
pages = "155--164",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366235&count=64&index=16;
http://ieeexplore.ieee.org/iel5/9430/29918/01366235.pdf?isnumber=29918&prod=CNF&arnumber=1366235&arSt=+155&ared=+164&arAuthor=Dinur%2C+I.%3B+Reingold%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Applebaum:2004:CNS,
author = "B. Applebaum and Y. Ishai and E. Kushilevitz",
title = "Cryptography in {NC}$^0$",
crossref = "IEEE:2004:PAI",
pages = "166--175",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366236&count=64&index=17;
http://ieeexplore.ieee.org/iel5/9430/29918/01366236.pdf?isnumber=29918&prod=CNF&arnumber=1366236&arSt=+166&ared=+175&arAuthor=Applebaum%2C+B.%3B+Ishai%2C+Y.%3B+Kushilevitz%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Vadhan:2004:USC,
author = "S. P. Vadhan",
title = "An unconditional study of computational zero
knowledge",
crossref = "IEEE:2004:PAI",
pages = "176--185",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366237&count=64&index=18;
http://ieeexplore.ieee.org/iel5/9430/29918/01366237.pdf?isnumber=29918&prod=CNF&arnumber=1366237&arSt=+176&ared=+185&arAuthor=Vadhan%2C+S.P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2004:UCP,
author = "B. Barak and R. Canetti and J. B. Nielsen and R.
Pass",
title = "Universally composable protocols with relaxed set-up
assumptions",
crossref = "IEEE:2004:PAI",
pages = "186--195",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366238&count=64&index=19;
http://ieeexplore.ieee.org/iel5/9430/29918/01366238.pdf?isnumber=29918&prod=CNF&arnumber=1366238&arSt=+186&ared=+195&arAuthor=Barak%2C+B.%3B+Canetti%2C+R.%3B+Nielsen%2C+J.B.%3B+Pass%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dodis:2004:IPC,
author = "Y. Dodis and Shien Jin Ong and M. Prabhakaran and A.
Sahai",
title = "On the (im)possibility of cryptography with imperfect
randomness",
crossref = "IEEE:2004:PAI",
pages = "196--205",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366239&count=64&index=20;
http://ieeexplore.ieee.org/iel5/9430/29918/01366239.pdf?isnumber=29918&prod=CNF&arnumber=1366239&arSt=+196&ared=+205&arAuthor=Dodis%2C+Y.%3B+Shien+Jin+Ong%3B+Prabhakaran%2C+M.%3B+Sahai%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dean:2004:ASK,
author = "B. C. Dean and M. X. Goemans and J. Vondrdk",
title = "Approximating the stochastic knapsack problem: the
benefit of adaptivity",
crossref = "IEEE:2004:PAI",
pages = "208--217",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366240&count=64&index=21;
http://ieeexplore.ieee.org/iel5/9430/29918/01366240.pdf?isnumber=29918&prod=CNF&arnumber=1366240&arSt=+208&ared=+217&arAuthor=Dean%2C+B.C.%3B+Goemans%2C+M.X.%3B+Vondrdk%2C+J.",
acknowledgement = ack-nhfb,
}
@InProceedings{Gupta:2004:ETS,
author = "A. Gupta and R. Ravi and A. Sinha",
title = "An edge in time saves nine: {LP} rounding
approximation algorithms for stochastic network
design",
crossref = "IEEE:2004:PAI",
pages = "218--227",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366241&count=64&index=22;
http://ieeexplore.ieee.org/iel5/9430/29918/01366241.pdf?isnumber=29918&prod=CNF&arnumber=1366241&arSt=+218&ared=+227&arAuthor=Gupta%2C+A.%3B+Ravi%2C+R.%3B+Sinha%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Shmoys:2004:SOA,
author = "D. B. Shmoys and C. Swamy",
title = "Stochastic optimization is (almost) as easy as
deterministic optimization",
crossref = "IEEE:2004:PAI",
pages = "228--237",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366242&count=64&index=23;
http://ieeexplore.ieee.org/iel5/9430/29918/01366242.pdf?isnumber=29918&prod=CNF&arnumber=1366242&arSt=+228&ared=+237&arAuthor=Shmoys%2C+D.B.%3B+Swamy%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Arora:2004:ASC,
author = "S. Arora and E. Hazan and S. Kale",
title = "{$O(\sqrt{\log n})$} approximation to {SPARSEST CUT}
in {$\tilde{O}(n^2)$} time",
crossref = "IEEE:2004:PAI",
pages = "238--247",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366243&count=64&index=24;
http://ieeexplore.ieee.org/iel5/9430/29918/01366243.pdf?isnumber=29918&prod=CNF&arnumber=1366243&arSt=+238&ared=+247&arAuthor=Arora%2C+S.%3B+Hazan%2C+E.%3B+Kale%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Mucha:2004:MMG,
author = "M. Mucha and P. Sankowski",
title = "Maximum matchings via {Gaussian} elimination",
crossref = "IEEE:2004:PAI",
pages = "248--255",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366244&count=64&index=25;
http://ieeexplore.ieee.org/iel5/9430/29918/01366244.pdf?isnumber=29918&prod=CNF&arnumber=1366244&arSt=+248&ared=+255&arAuthor=Mucha%2C+M.%3B+Sankowski%2C+P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Savani:2004:EMS,
author = "R. Savani and B. von Stengel",
title = "Exponentially many steps for finding a {Nash}
equilibrium in a bimatrix game",
crossref = "IEEE:2004:PAI",
pages = "258--267",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366245&count=64&index=26;
http://ieeexplore.ieee.org/iel5/9430/29918/01366245.pdf?isnumber=29918&prod=CNF&arnumber=1366245&arSt=+258&ared=+267&arAuthor=Savani%2C+R.%3B+von+Stengel%2C+B.",
acknowledgement = ack-nhfb,
}
@InProceedings{Karakostas:2004:EPM,
author = "G. Karakostas and S. G. Kolliopoulos",
title = "Edge pricing of multicommodity networks for
heterogeneous selfish users",
crossref = "IEEE:2004:PAI",
pages = "268--276",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366246&count=64&index=27;
http://ieeexplore.ieee.org/iel5/9430/29918/01366246.pdf?isnumber=29918&prod=CNF&arnumber=1366246&arSt=+268&ared=+276&arAuthor=Karakostas%2C+G.%3B+Kolliopoulos%2C+S.G.",
acknowledgement = ack-nhfb,
}
@InProceedings{Fleischer:2004:THS,
author = "L. Fleischer and K. Jain and M. Mahdian",
title = "Tolls for heterogeneous selfish users in
multicommodity networks and generalized congestion
games",
crossref = "IEEE:2004:PAI",
pages = "277--285",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366247&count=64&index=28;
http://ieeexplore.ieee.org/iel5/9430/29918/01366247.pdf?isnumber=29918&prod=CNF&arnumber=1366247&arSt=+277&ared=+285&arAuthor=Fleischer%2C+L.%3B+Jain%2C+K.%3B+Mahdian%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Jain:2004:PTA,
author = "K. Jain",
title = "A polynomial time algorithm for computing an
{Arrow--Debreu} market equilibrium for linear
utilities",
crossref = "IEEE:2004:PAI",
pages = "286--294",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366248&count=64&index=29;
http://ieeexplore.ieee.org/iel5/9430/29918/01366248.pdf?isnumber=29918&prod=CNF&arnumber=1366248&arSt=+286&ared=+294&arAuthor=Jain%2C+K.",
acknowledgement = ack-nhfb,
}
@InProceedings{Anshelevich:2004:PSN,
author = "E. Anshelevich and A. Dasgupta and J. Kleinberg and E.
Tardos and T. Wexler and T. Roughgarden",
title = "The price of stability for network design with fair
cost allocation",
crossref = "IEEE:2004:PAI",
pages = "295--304",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366249&count=64&index=30;
http://ieeexplore.ieee.org/iel5/9430/29918/01366249.pdf?isnumber=29918&prod=CNF&arnumber=1366249&arSt=+295&ared=+304&arAuthor=Anshelevich%2C+E.%3B+Dasgupta%2C+A.%3B+Kleinberg%2C+J.%3B+Tardos%2C+E.%3B+Wexler%2C+T.%3B+Roughgarden%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Valiant:2004:HA,
author = "L. G. Valiant",
title = "Holographic algorithms",
crossref = "IEEE:2004:PAI",
pages = "306--315",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366250&count=64&index=31;
http://ieeexplore.ieee.org/iel5/9430/29918/01366250.pdf?isnumber=29918&prod=CNF&arnumber=1366250&arSt=+306&ared=+315&arAuthor=Valiant%2C+L.G.",
acknowledgement = ack-nhfb,
}
@InProceedings{Fortnow:2004:HTP,
author = "L. Fortnow and R. Santhanam",
title = "Hierarchy theorems for probabilistic polynomial time",
crossref = "IEEE:2004:PAI",
pages = "316--324",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366251&count=64&index=32;
http://ieeexplore.ieee.org/iel5/9430/29918/01366251.pdf?isnumber=29918&prod=CNF&arnumber=1366251&arSt=+316&ared=+324&arAuthor=Fortnow%2C+L.%3B+Santhanam%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Langberg:2004:PCS,
author = "M. Langberg",
title = "Private codes or succinct random codes that are
(almost) perfect",
crossref = "IEEE:2004:PAI",
pages = "325--334",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366252&count=64&index=33;
http://ieeexplore.ieee.org/iel5/9430/29918/01366252.pdf?isnumber=29918&prod=CNF&arnumber=1366252&arSt=+325&ared=+334&arAuthor=Langberg%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Cheng:2004:LBD,
author = "Qi Cheng and Daqing Wan",
title = "On the list and bounded distance decodibility of
{Reed--Solomon} codes",
crossref = "IEEE:2004:PAI",
pages = "335--341",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366253&count=64&index=34;
http://ieeexplore.ieee.org/iel5/9430/29918/01366253.pdf?isnumber=29918&prod=CNF&arnumber=1366253&arSt=+335&ared=+341&arAuthor=Qi+Cheng%3B+Daqing+Wan",
acknowledgement = ack-nhfb,
}
@InProceedings{Raz:2004:MNS,
author = "R. Raz",
title = "Multilinear-{NC}$_1$ $\neq$ multilinear-{NC}$_2$",
crossref = "IEEE:2004:PAI",
pages = "344--351",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366254&count=64&index=35;
http://ieeexplore.ieee.org/iel5/9430/29918/01366254.pdf?isnumber=29918&prod=CNF&arnumber=1366254&arSt=+344&ared=+351&arAuthor=Raz%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chien:2004:API,
author = "S. Chien and A. Sinclair",
title = "Algebras with polynomial identities and computing the
determinant",
crossref = "IEEE:2004:PAI",
pages = "352--361",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366255&count=64&index=36;
http://ieeexplore.ieee.org/iel5/9430/29918/01366255.pdf?isnumber=29918&prod=CNF&arnumber=1366255&arSt=+352&ared=+361&arAuthor=Chien%2C+S.%3B+Sinclair%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Aharonov:2004:LPN,
author = "D. Aharonov and O. Regev",
title = "Lattice problems in {NP} $\cap$ {coNP}",
crossref = "IEEE:2004:PAI",
pages = "362--371",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366256&count=64&index=37;
http://ieeexplore.ieee.org/iel5/9430/29918/01366256.pdf?isnumber=29918&prod=CNF&arnumber=1366256&arSt=+362&ared=+371&arAuthor=Aharonov%2C+D.%3B+Regev%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Micciancio:2004:WCA,
author = "D. Micciancio and O. Regev",
title = "Worst-case to average-case reductions based on
{Gaussian} measures",
crossref = "IEEE:2004:PAI",
pages = "372--381",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366257&count=64&index=38;
http://ieeexplore.ieee.org/iel5/9430/29918/01366257.pdf?isnumber=29918&prod=CNF&arnumber=1366257&arSt=+372&ared=+381&arAuthor=Micciancio%2C+D.%3B+Regev%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Barak:2004:ERU,
author = "B. Barak and R. Impagliazzo and A. Wigderson",
title = "Extracting randomness using few independent sources",
crossref = "IEEE:2004:PAI",
pages = "384--393",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366258&count=64&index=39;
http://ieeexplore.ieee.org/iel5/9430/29918/01366258.pdf?isnumber=29918&prod=CNF&arnumber=1366258&arSt=+384&ared=+393&arAuthor=Barak%2C+B.%3B+Impagliazzo%2C+R.%3B+Wigderson%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Gabizon:2004:DEB,
author = "A. Gabizon and R. Raz and R. Shaltiel",
title = "Deterministic extractors for bit-fixing sources by
obtaining an independent seed",
crossref = "IEEE:2004:PAI",
pages = "394--403",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366259&count=64&index=40;
http://ieeexplore.ieee.org/iel5/9430/29918/01366259.pdf?isnumber=29918&prod=CNF&arnumber=1366259&arSt=+394&ared=+403&arAuthor=Gabizon%2C+A.%3B+Raz%2C+R.%3B+Shaltiel%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bilu:2004:CEG,
author = "Y. Bilu and N. Linial",
title = "Constructing expander graphs by $2$-lifts and
discrepancy vs. spectral gap",
crossref = "IEEE:2004:PAI",
pages = "404--412",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366260&count=64&index=41;
http://ieeexplore.ieee.org/iel5/9430/29918/01366260.pdf?isnumber=29918&prod=CNF&arnumber=1366260&arSt=+404&ared=+412&arAuthor=Bilu%2C+Y.%3B+Linial%2C+N.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kaufman:2004:TPG,
author = "T. Kaufman and D. Ron",
title = "Testing polynomials over general fields",
crossref = "IEEE:2004:PAI",
pages = "413--422",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366261&count=64&index=42;
http://ieeexplore.ieee.org/iel5/9430/29918/01366261.pdf?isnumber=29918&prod=CNF&arnumber=1366261&arSt=+413&ared=+422&arAuthor=Kaufman%2C+T.%3B+Ron%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Jutla:2004:TLD,
author = "C. S. Jutla and A. C. Patthak and A. Rudra and D.
Zuckerman",
title = "Testing low-degree polynomials over prime fields",
crossref = "IEEE:2004:PAI",
pages = "423--432",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366262&count=64&index=43;
http://ieeexplore.ieee.org/iel5/9430/29918/01366262.pdf?isnumber=29918&prod=CNF&arnumber=1366262&arSt=+423&ared=+432&arAuthor=Jutla%2C+C.S.%3B+Patthak%2C+A.C.%3B+Rudra%2C+A.%3B+Zuckerman%2C+D.",
acknowledgement = ack-nhfb,
}
@InProceedings{Krauthgamer:2004:MDN,
author = "R. Krauthgamer and J. R. Lee and M. Mendel and A.
Naor",
title = "Measured descent: a new embedding method for finite
metrics",
crossref = "IEEE:2004:PAI",
pages = "434--443",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366263&count=64&index=44;
http://ieeexplore.ieee.org/iel5/9430/29918/01366263.pdf?isnumber=29918&prod=CNF&arnumber=1366263&arSt=+434&ared=+443&arAuthor=Krauthgamer%2C+R.%3B+Lee%2C+J.R.%3B+Mendel%2C+M.%3B+Naor%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kleinberg:2004:TEU,
author = "J. Kleinberg and A. Slivkins and T. Wexler",
title = "Triangulation and embedding using small sets of
beacons",
crossref = "IEEE:2004:PAI",
pages = "444--453",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366264&count=64&index=45;
http://ieeexplore.ieee.org/iel5/9430/29918/01366264.pdf?isnumber=29918&prod=CNF&arnumber=1366264&arSt=+444&ared=+453&arAuthor=Kleinberg%2C+J.%3B+Slivkins%2C+A.%3B+Wexler%2C+T.",
acknowledgement = ack-nhfb,
}
@InProceedings{Kumar:2004:SLT,
author = "A. Kumar and Y. Sabharwal and S. Sen",
title = "A simple linear time $(1 + \epsilon)$-approximation
algorithm for $k$-means clustering in any dimensions",
crossref = "IEEE:2004:PAI",
pages = "454--462",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366265&count=64&index=46;
http://ieeexplore.ieee.org/iel5/9430/29918/01366265.pdf?isnumber=29918&prod=CNF&arnumber=1366265&arSt=+454&ared=+462&arAuthor=Kumar%2C+A.%3B+Sabharwal%2C+Y.%3B+Sen%2C+S.",
acknowledgement = ack-nhfb,
}
@InProceedings{Halman:2004:PDL,
author = "N. Halman",
title = "On the power of discrete and of lexicographic
{Helly}-type theorems",
crossref = "IEEE:2004:PAI",
pages = "463--472",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366266&count=64&index=47;
http://ieeexplore.ieee.org/iel5/9430/29918/01366266.pdf?isnumber=29918&prod=CNF&arnumber=1366266&arSt=+463&ared=+472&arAuthor=Halman%2C+N.",
acknowledgement = ack-nhfb,
}
@InProceedings{Chakrabarti:2004:ORC,
author = "A. Chakrabarti and O. Regev",
title = "An optimal randomised cell probe lower bound for
approximate nearest neighbour searching",
crossref = "IEEE:2004:PAI",
pages = "473--482",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366267&count=64&index=48;
http://ieeexplore.ieee.org/iel5/9430/29918/01366267.pdf?isnumber=29918&prod=CNF&arnumber=1366267&arSt=+473&ared=+482&arAuthor=Chakrabarti%2C+A.%3B+Regev%2C+O.",
acknowledgement = ack-nhfb,
}
@InProceedings{Demaine:2004:DOA,
author = "E. D. Demaine and D. Harmon and J. Iacono and M.
Patrascu",
title = "Dynamic optimality --- almost [competitive online
binary search tree]",
crossref = "IEEE:2004:PAI",
pages = "484--490",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366268&count=64&index=49;
http://ieeexplore.ieee.org/iel5/9430/29918/01366268.pdf?isnumber=29918&prod=CNF&arnumber=1366268&arSt=+484&ared=+490&arAuthor=Demaine%2C+E.D.%3B+Harmon%2C+D.%3B+Iacono%2C+J.%3B+Patrascu%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Franceschini:2004:NSB,
author = "G. Franceschini and R. Grossi",
title = "No sorting? {Better} searching! [optimal array
organization]",
crossref = "IEEE:2004:PAI",
pages = "491--498",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366269&count=64&index=50;
http://ieeexplore.ieee.org/iel5/9430/29918/01366269.pdf?isnumber=29918&prod=CNF&arnumber=1366269&arSt=+491&ared=+498&arAuthor=Franceschini%2C+G.%3B+Grossi%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Roditty:2004:DAA,
author = "L. Roditty and U. Zwick",
title = "Dynamic approximate all-pairs shortest paths in
undirected graphs",
crossref = "IEEE:2004:PAI",
pages = "499--508",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366270&count=64&index=51;
http://ieeexplore.ieee.org/iel5/9430/29918/01366270.pdf?isnumber=29918&prod=CNF&arnumber=1366270&arSt=+499&ared=+508&arAuthor=Roditty%2C+L.%3B+Zwick%2C+U.",
acknowledgement = ack-nhfb,
}
@InProceedings{Sankowski:2004:DTC,
author = "P. Sankowski",
title = "Dynamic transitive closure via dynamic matrix inverse:
extended abstract",
crossref = "IEEE:2004:PAI",
pages = "509--517",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366271&count=64&index=52;
http://ieeexplore.ieee.org/iel5/9430/29918/01366271.pdf?isnumber=29918&prod=CNF&arnumber=1366271&arSt=+509&ared=+517&arAuthor=Sankowski%2C+P.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bansal:2004:DSS,
author = "N. Bansal and T. Kimbrel and K. Pruhs",
title = "Dynamic speed scaling to manage energy and
temperature",
crossref = "IEEE:2004:PAI",
pages = "520--529",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366272&count=64&index=53;
http://ieeexplore.ieee.org/iel5/9430/29918/01366272.pdf?isnumber=29918&prod=CNF&arnumber=1366272&arSt=+520&ared=+529&arAuthor=Bansal%2C+N.%3B+Kimbrel%2C+T.%3B+Pruhs%2C+K.",
acknowledgement = ack-nhfb,
}
@InProceedings{Augustine:2004:OPS,
author = "J. Augustine and S. Irani and C. Swamy",
title = "Optimal power-down strategies",
crossref = "IEEE:2004:PAI",
pages = "530--539",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366273&count=64&index=54;
http://ieeexplore.ieee.org/iel5/9430/29918/01366273.pdf?isnumber=29918&prod=CNF&arnumber=1366273&arSt=+530&ared=+539&arAuthor=Augustine%2C+J.%3B+Irani%2C+S.%3B+Swamy%2C+C.",
acknowledgement = ack-nhfb,
}
@InProceedings{Aggarwal:2004:SMA,
author = "G. Aggarwal and M. Datar and S. Rajagopalan and M.
Ruhl",
title = "On the streaming model augmented with a sorting
primitive",
crossref = "IEEE:2004:PAI",
pages = "540--549",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366274&count=64&index=55;
http://ieeexplore.ieee.org/iel5/9430/29918/01366274.pdf?isnumber=29918&prod=CNF&arnumber=1366274&arSt=+540&ared=+549&arAuthor=Aggarwal%2C+G.%3B+Datar%2C+M.%3B+Rajagopalan%2C+S.%3B+Ruhl%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bar-Yossef:2004:AED,
author = "Z. Bar-Yossef and T. S. Jayram and R. Krauthgamer and
R. Kumar",
title = "Approximating edit distance efficiently",
crossref = "IEEE:2004:PAI",
pages = "550--559",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366275&count=64&index=56;
http://ieeexplore.ieee.org/iel5/9430/29918/01366275.pdf?isnumber=29918&prod=CNF&arnumber=1366275&arSt=+550&ared=+559&arAuthor=Bar-Yossef%2C+Z.%3B+Jayram%2C+T.S.%3B+Krauthgamer%2C+R.%3B+Kumar%2C+R.",
acknowledgement = ack-nhfb,
}
@InProceedings{Goldberg:2004:SSM,
author = "L. A. Goldberg and R. Martin and M. Paterson",
title = "Strong spatial mixing for lattice graphs with fewer
colours",
crossref = "IEEE:2004:PAI",
pages = "562--571",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366276&count=64&index=57;
http://ieeexplore.ieee.org/iel5/9430/29918/01366276.pdf?isnumber=29918&prod=CNF&arnumber=1366276&arSt=+562&ared=+571&arAuthor=Goldberg%2C+L.A.%3B+Martin%2C+R.%3B+Paterson%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Mossel:2004:SSR,
author = "E. Mossel and Y. Peres and A. Sinclair",
title = "Shuffling by semi-random transpositions",
crossref = "IEEE:2004:PAI",
pages = "572--581",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366277&count=64&index=58;
http://ieeexplore.ieee.org/iel5/9430/29918/01366277.pdf?isnumber=29918&prod=CNF&arnumber=1366277&arSt=+572&ared=+581&arAuthor=Mossel%2C+E.%3B+Peres%2C+Y.%3B+Sinclair%2C+A.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dyer:2004:RCC,
author = "M. Dyer and A. Frieze and T. P. Hayes and E. Vigoda",
title = "Randomly coloring constant degree graphs",
crossref = "IEEE:2004:PAI",
pages = "582--589",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366278&count=64&index=59;
http://ieeexplore.ieee.org/iel5/9430/29918/01366278.pdf?isnumber=29918&prod=CNF&arnumber=1366278&arSt=+582&ared=+589&arAuthor=Dyer%2C+M.%3B+Frieze%2C+A.%3B+Hayes%2C+T.P.%3B+Vigoda%2C+E.",
acknowledgement = ack-nhfb,
}
@InProceedings{Connamacher:2004:EST,
author = "H. Connamacher and M. Molloy",
title = "The exact satisfiability threshold for a potentially
intractable random constraint satisfaction problem",
crossref = "IEEE:2004:PAI",
pages = "590--599",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366279&count=64&index=60;
http://ieeexplore.ieee.org/iel5/9430/29918/01366279.pdf?isnumber=29918&prod=CNF&arnumber=1366279&arSt=+590&ared=+599&arAuthor=Connamacher%2C+H.%3B+Molloy%2C+M.",
acknowledgement = ack-nhfb,
}
@InProceedings{Dasgupta:2004:SAR,
author = "A. Dasgupta and J. E. Hopcroft and F. McSherry",
title = "Spectral analysis of random graphs with skewed degree
distributions",
crossref = "IEEE:2004:PAI",
pages = "602--610",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366280&count=64&index=61;
http://ieeexplore.ieee.org/iel5/9430/29918/01366280.pdf?isnumber=29918&prod=CNF&arnumber=1366280&arSt=+602&ared=+610&arAuthor=Dasgupta%2C+A.%3B+Hopcroft%2C+J.E.%3B+McSherry%2C+F.",
acknowledgement = ack-nhfb,
}
@InProceedings{Bisht:2004:LEA,
author = "L. Bisht and N. H. Bshouty and L. Khoury",
title = "Learning with errors in answers to membership
queries",
crossref = "IEEE:2004:PAI",
pages = "611--620",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366281&count=64&index=62;
http://ieeexplore.ieee.org/iel5/9430/29918/01366281.pdf?isnumber=29918&prod=CNF&arnumber=1366281&arSt=+611&ared=+620&arAuthor=Bisht%2C+L.%3B+Bshouty%2C+N.H.%3B+Khoury%2C+L.",
acknowledgement = ack-nhfb,
}
@InProceedings{Alekhnovich:2004:LA,
author = "M. Alekhnovich and M. Braverman and V. Feldman and A.
R. Klivans and T. Pitassi",
title = "Learnability and automatizability",
crossref = "IEEE:2004:PAI",
pages = "621--630",
year = "2004",
bibdate = "Fri Jul 15 16:13:03 MDT 2005",
URL = "http://ieeexplore.ieee.org/xpls/abs_all.jsp?isnumber=29918&arnumber=1366282&count=64&index=63;
http://ieeexplore.ieee.org/iel5/9430/29918/01366282.pdf?isnumber=29918&prod=CNF&arnumber=1366282&arSt=+621&ared=+630&arAuthor=Alekhnovich%2C+M.%3B+Braverman%2C+M.%3B+Feldman%2C+V.%3B+Klivans%2C+A.R.%3B+Pitassi%2C+T.",
acknowledgement = ack-nhfb,
}
%%% ====================================================================
%%% Cross-referenced entries must come last:
@Proceedings{IEEE:2000:ASF,
editor = "{IEEE}",
booktitle = "{41st Annual Symposium on Foundations of Computer
Science: proceedings: 12--14 November, 2000, Redondo
Beach, California}",
title = "{41st Annual Symposium on Foundations of Computer
Science: proceedings: 12--14 November, 2000, Redondo
Beach, California}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xiv + 688",
year = "2000",
CODEN = "ASFPDV",
ISSN = "0272-5428",
ISBN = "0-7695-0850-2, 0-7695-0851-0 (case), 0-7695-0852-9
(microfiche)",
ISBN-13 = "978-0-7695-0850-4, 978-0-7695-0851-1 (case),
978-0-7695-0852-8 (microfiche)",
LCCN = "TK7885.A1 S92 2000",
bibdate = "Thu Apr 05 06:27:02 2001",
note = "IEEE Computer Society Order Number PR00850.",
acknowledgement = ack-nhfb,
}
@Proceedings{IEEE:2001:ISF,
editor = "{IEEE}",
booktitle = "{42nd IEEE Symposium on Foundations of Computer
Science: proceedings: October 14--17, 2001, Las Vegas,
Nevada, USA}",
title = "{42nd IEEE Symposium on Foundations of Computer
Science: proceedings: October 14--17, 2001, Las Vegas,
Nevada, USA}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xiii + 670",
year = "2001",
CODEN = "ASFPDV",
ISSN = "0272-5428",
ISBN = "0-7695-1390-5, 0-7695-1391-3 (case), 0-7695-1392-1
(microfiche)",
ISBN-13 = "978-0-7695-1390-4, 978-0-7695-1391-1 (case),
978-0-7695-1392-8 (microfiche)",
LCCN = "????",
bibdate = "Thu Feb 21 19:19:40 2002",
acknowledgement = ack-nhfb,
}
@Proceedings{IEEE:2002:PAI,
editor = "{IEEE}",
booktitle = "{Proceedings of the 43rd Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2002, Vancouver,
BC, Canada, 16--19 November 2002}",
title = "{Proceedings of the 43rd Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2002, Vancouver,
BC, Canada, 16--19 November 2002}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xvi + 813",
year = "2002",
CODEN = "ASFPDV",
DOI = "http://dx.doi.org/10.1109/SFCS.2002.1181875",
ISBN = "0-7695-1822-2",
ISBN-13 = "978-0-7695-1822-0",
ISSN = "0272-5428",
LCCN = "QA267",
bibdate = "Fri Jul 15 14:24:23 2005",
note = "IEEE Computer Society Order Number PR01822",
URL = "http://ieeexplore.ieee.org/iel5/8411/26517/01181875.pdf",
acknowledgement = ack-nhfb,
}
@Proceedings{IEEE:2003:PAI,
editor = "{IEEE}",
booktitle = "{Proceedings: 44th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2003, 11--14
October 2003, Cambridge, Massachusetts}",
title = "{Proceedings: 44th Annual IEEE Symposium on
Foundations of Computer Science, FOCS 2003, 11--14
October 2003, Cambridge, Massachusetts}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xiii + 661",
year = "2003",
CODEN = "ASFPDV",
ISBN = "0-7695-2040-5",
ISBN-13 = "978-0-7695-2040-7",
ISSN = "0272-5428",
LCCN = "QA76 .S979 2003",
bibdate = "Fri Jul 15 14:29:27 2005",
note = "IEEE Computer Society Order Number PR02040.",
URL = "http://ieeexplore.ieee.org/xpl/RecentCon.jsp?punumber=8767&conhome=1000292;
http://ieeexplore.ieee.org/iel5/8767/27770/01238173.pdf",
acknowledgement = ack-nhfb,
}
@Proceedings{IEEE:2004:PAI,
editor = "{IEEE}",
booktitle = "{Proceedings: 45th Annual IEEE Symposium on
Foundations of Computer Science: FOCS 2004, 17--19
October, 2004, Rome, Italy}",
title = "{Proceedings: 45th Annual IEEE Symposium on
Foundations of Computer Science: FOCS 2004, 17--19
October, 2004, Rome, Italy}",
publisher = pub-IEEE,
address = pub-IEEE:adr,
pages = "xiv + 632",
year = "2004",
CODEN = "ASFPDV",
ISBN = "0-7695-2228-9",
ISBN-13 = "978-0-7695-2228-9",
ISSN = "0272-5428",
LCCN = "QA276",
bibdate = "Fri Jul 15 14:47:05 MDT 2005",
bibsource = "melvyl.cdlib.org:210/CDL90",
note = "IEEE Computer Society Order Number P2228",
URL = "http://ieeexplore.ieee.org/servlet/opac?punumber=9430;
http://ieeexplore.ieee.org/iel5/9430/29918/01366212.pdf",
acknowledgement = ack-nhfb,
subject = "Electronic data processing; Congresses; Machine
theory; Congresses",
}