%%% -*-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",