http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2002.html
STOC 2002
http://doi.acm.org/10.1145/509907.509938	23	Optimal Rate-based Scheduling on Multiprocessors ∗	adler algorithm algorithmica algorithms allocation anderson application applications asynchronous baruah based beyond bridging cation certain chandra cient ciently cohen computing concluding conditions conference connection correctly currently date deadline design development distinguish distributed division domains early either environment erfair euromicro execution exist facilitate fair fairness fast feasible fourth from fundamental gehrke goddard goyal hard have holes identi ieee implementation insights intra investigating jacm joint june layland make minimality mixed model more most multiple multiplexing multiprocessor multiprocessors multiprogramming networks nitions notion notions operating optimal optimally oriented osdi packet paper paral parallel periodic pfair plaxton potential potentially practice predict previous problems proc processing processors progress proof proofs properties proportional proportionate proposed rate real reasoning references release remarks report researchers resource resources schedule scheduled schedules scheduling servers several share shenoy show shown sporadic srinivasan state surplus switching symmetric symp symposium system systems task tasks technical technology than that theory these this time university used useful using varvel wave where with work
http://doi.acm.org/10.1145/509907.509929	16	Lower Bounds & Competitive Algorithms for Online Scheduling of Unit-Size Tasks to Related Machines∗	achieve actually adap adaptive additionally advances alfonsin algorithmic algorithms allo already also amount analysis annual another appear applications arbitrary aspects aspens assigned assignment assures asymmetry asymptotically available avoidance azar balanced balancing ballanced balls because become behaviour being berenbrink berman bins boro bottlenecks bounds cambridge cantly case category cations charikar choices circuit cking communication competitive computation computational computer computing conclusions consequence corless cost critical cumulative czuma data deal dealt design deteriorate determined discrete during eecs eginger eligible enough equilibria expected exploiting fail fall fiat focs following francisco free freund function further gonnet granted habib handbo hare harvard hash have heavily helps http ideal identical ieee inequality information injected input interesting into isbn issue jective jobs journal karlin karpinski knuth koutsoupias krete lambert lemma length less limited line lncs load loaded longest machine machines make many mathematics mavronicolas mcdiarmid metho michaelm mimics minimization mitzenmacher most must naor network nition oblivious observe online only optc optimal optimally order papadimitriou parallel perform performance plotkin portland power press previous price probabilistic probe problem problems prove providing raab ramirez random randomized recall reed reen references related remaining remains research results richa roughly routing saturated scheduler schedulers scheduling science searching sequence served setting sgall shmoys shown siam signi similar simple sitaraman size sizes soda space spirakis springer stacs stage state steger stoc straightforward structures studied study such survey symposium system task tasks techniques temporary than that then theorem theoretical this through thus tight unit univ upfal uses using velrag verlag very virtual vocking waarts wein which williamson with work workshop worst would yaniv york
http://doi.acm.org/10.1145/509907.510018	87	Learnability Beyond AC0	able above abstract adaboost additive after algorithm algorithmica algorithms also always amherst analysis annual appendix apply approach approaches approximately approximating approximator argue aspnes assumptions balance based baum been beigel better blum blumer boolean boosting bottom bounded bounds breaks bruck bshouty cally cambridge cannot case causes change changes chervonenkis choice choose choosing cient ciently circuit circuits class close closed codes coefficients combinatorica combined combines communications complexity computation computational compute computed computer computing conceivable conclude conference consider constant constraints construct constructed constructions contains continuing core correcting correlated correlation corresponding could cryptographic current decision denote depth described dimension discrete disjoint distinct distributed distribution distributions does domingo done down each easily ehrenfeucht eighth equivalence equivalent erent error essential european even every exact example examples except exclusion execution exhibit exponential exponentially expressive extended extensions extra factor feed feel fibonacci fifth following follows form formulae formulas fortieth found foundations fourier fourteenth freund frieze from function functions furst gate gates gavinsky geometric given gives greater halfspaces hard hardness harmonic harvard hastad haussler have help hidden hold holland however hypothesis identify implies inclusion index information initial inner input integer interesting intersection interval intervals into inverse itself jackson jnal jority journal kannan kearns kharitonov klivans know known krause lead learn learnability learnable learning learns leaves lemma length less lest letters level lies like limitations linear linial lists lowing lows maass macwilliams madaboost majority make mansour massachusetts master mathematics membership methods models modi modulo monotone more moreover most multiple multiplicative must naor negative negatives nets neural next nisan noisy nonnegligibly north note number numbers observation observed observing omitted only open optimal other otherwise outlier output outputs over pages parity partition perceptron perhaps placed poly polylog polylogarithmic polynomial polynomials positive positives possibility possibly potentially power precisely press prime proceedings process processing produced product programming proof property proved pseudo pudlak quasipolynomial queries query random rank real reasonably references reingold removal required respect root round rudich same sampling satis science sciences second section servedio sets share shared shift show shown siam similarly simple simply since single sixth size sloane smal small some speci spectrum spielman step still strategy string strong strongly subclass subexponential succeed such symmetric symposium system szegedy take taken tamon target tarui techniques than that then theoretic theory there these thesis third thirteenth thirty this threshold thus time transform trees tsukiji turan twenty under uniform uniformly union unit university used useful using valiant value valued vapnik variables vary vempala veri versa version very vice viewed voting warmuth watanabe weak weakly weight weights when where whether which while whose will with without workshop would york zhang
http://doi.acm.org/10.1145/509907.509966	45	Fast, Small-Space Algorithms for Approximate Histogram Maintenance	aboulnaga additional aggregate algorithm algorithms alon analysis approximate approximating approximation array based basis best bounded bucket building cannot change chaudhuri choices chung communication complexity compressed computation consider construct data demand dimacs dimensional directly discarding distributions dynamic each elements embeddings erence error estimation evaluation every extension extensions fast feigenbaum finally focs follows form frequency generators gibbons gilbert goes guarantees guha halting have hence high histogram histograms hopt icde implicitly including incremental indyk information integer intervals into jagadish jcss joptj kannan kotidis koudas least length looking madison maintenance march massive matias minimum moments more most multi multidimensional muthukrishnan naor near need negative network never nisan nition operations optimal other otherwise ould over pass performance poly poosala positive possible private probability process produce produced production proof proves pseudorandom quality queries querying quick quicksand random references reingold report representation requires retained robust second selecitivty selectivity self sets sevcik shim show sigmod signal since size sjoptj sketch soda some space stable statement step stoc strauss stream streams structure structures such suel summaries summary supports suppose synopsis szegedy technical than thaper that then theorem there thesis this thus time tograms tuning under updates useful using viswanathan vitter vldb wang wavelet wavelets where will wisconsin with without
http://doi.acm.org/10.1145/509907.510004	75	Expanders from Symmetric Codes	acad academic access algebras alon amer application applications aschbacher associated basel birkhauser brown buhler cambridge carter case cation character classes classi combin combinatorial combinatorica comp complete compt computer concentrators condition connections constant construction constructions degree density design dimacs direct discr discrete eigenvalues entropy even every expanders expanding explicit exponential extractors finite focs forum fredman friedman from functions gabber galil generalizations generalized generated generators geometric gons graph graphs group groups growth harpe hash holds inequalities inform information invariant isaacs isoperimetric israel jordan journal kazhdan komlos large linear lubotzky mann margulis math measures meth milman namely nite nitely note pages philips positively post press problems proc product proof property proving pyber ramanujan ramsey references reingold rewrite robertson same sarnak satis schemes sciences semi sets shalev siam since singleton sized small solvability sparse spectrum storing subgroup super superconcentrators support system szemer table taketa tanner that their theorem theoret theoretical theory thus time transmission universal university vadhan valette vector verlag version wassermann waves wegman weisfeiler weiss wigderson will with worst york
http://doi.acm.org/10.1145/509907.509950	32	Cache-Oblivious Priori ty Queue and Graph Algorithm Applications	academic acta addison aggarwal algorithm algorithmica algorithmics algorithms analysis anderson annual applications approach approximate architectures arge bayer bender biconnectivity binary block blumofe brodal buchsbaum cache caches carter case chandra chen chiang chin cient coin cole colton combinatorics comer communications comp complexity computation computer computing conference connection consistent control data dealing decision decomp demaine deterministic diagram dictionary discrete distributed duan dynamic edition editors ello engineering erformance european experimental extending external fadel fagerb farach feig foundations frigo functional generalizations goldwasser goodrich graph grove handbook heaps heapsort height hierachies hierarchical hierarchy hong huddleston iacono ieee improved indexes informatica information input internal international jacob jainen jakobsen joerg journal kata kluwer knuth kumar kung ladner lamarca large leiserson letters list lists lncs locality logarithmic maintenance manipulation massive matrix mccreight mehlhorn memories memory miller model multi multilevel munagala networks oblivious optimal optimized ordered organization orientation osition output pages paral parallel pardalos partial pivoting planar predecessor preserving prim priority problems proc proceedings processing programming prokop publishers queues rahman ramachandran raman ranade randall randomized ranking reading reference references related representing resende savage scandinavian scheduling schwab science search searching second secondary selker separation sets shared shortest shriver siam simple small snir solving some sorted sorting sssp storage strong structure structures surveys symp symposium syst tamas tarjan tech technique teuhola theoretical theory time toledo toma tossing transfer traversal tree trees ubiquitous uence uniform vengro venkatasubramanian virtual vishkin vitter volume wesley westbrook with workshop worst
http://doi.acm.org/10.1145/509907.510003	74	Randomness Conductors and Constant-Degree Lossless Expanders	abstract alekhnovich algebraic algorithms alon annual applications approach arora atlanta beach beame binomial bits bitvectors bounded bounds broder buhrman bureau calculus california capalbo case check chor codes colloquium combinatorial combinatorica communication complexity comput computation computational computer computing concentrators condensers condensing constant constructing construction constructions constructive consultants correcting decodable degree density depth derivations discrete disjoint distributed dynamic eigenvalues electronic encodable entropy error examples expander expanders expansion explicit extended extracting extractors families first florida foundations frieze from functions future generalized generators goldreich gons graph graphs group hard hashing ieee improved inform informatsii irregular island journal july june kahale leighton less line linear logic london loss lower lubotzky luby made maggs many march margulis mathematical mathematics memory methods miami milman miltersen mitzenmacher narrow neighbor network nisan nonblocking optimal pages parity part past path paths peleg peredachi phillips pippenger pitassi polynomial preprint present private probabilistic problemy proc proceedings product proof proofs properties propositional pseudorandom quality radhakrishnan ramanujan random randomness razborov recycling redondo reducing references regular reingold repeated report resolution revised rounds sarnak sasson schemes science second selecting selection sept shaltiel share shma shokrollahi short siam simple singer sipser size sorting sources space spielman srinivasan states static structures studies submitted superconcentrators symposium syst system szemer tanner technical their theoretic theory thirty tight time tiny trade trans trevisan tseitin umans unbalanced unbiased unique upfal urquhart using vadhan version versus very walk waves weak wigderson with york zuckerman
http://doi.acm.org/10.1145/509907.509912	2	New Results on Monotone Dualization and Generating Hypergraph Transversals	academic acta acyclic acyclicity algorithm algorithmic algorithmica algorithms annals annual antikeys appear application applied armstrong arti aspects automata avoid beigel between bioch boolean bounded canada cataloging cation chapter characteristic chordality cial cient closed coherent colouring colt combinatorial combinatorics completeness complexity compsac comput computation computational computations computer computing conference coteries cybernetica data database decompositions degree design diagnosis dimacs discrete disjunctive distributed dual dualization elsevier envelopes erice every example exclusion fast first fischer forms from full function functions games generating given goldsmith gottlob graham graph graphs gunopulos gurations gurvich handbook hardness horn hypergraph hypergraphs hypertree ibaraki icalp identi identifying ieee independent information intel international isaac isomorphism italy johnson journal june kameda kavvadias keys khardon kintala kluwer languages latency lawler learning lecture lenstra leone letters levy ligence limited linear lncs loquium machine makino mannila math mathematics maximal maximum membership minimal mining minors mishra models molecular monotone monotonic mundhenk mutual nash news ning nondeterminism normal open optimization osaka ozsoyoglu papadimitriou paper paral peled perfect phys pitt pods polynomial positive principles problems proc proceedings processing programming publishers pure queries query ramamurthy read recursion reduce references regular reiter relation relations relativized report representations research retrospective rinnooy robertson rutcor rutgers scarcello school science sciences selectively september sets seymour siam sideri sigact simeone simple solvability some springer stable stampacchia strategies structures summer symp symposium system systems tarjan technical tenth term test their theory time toft toivonen toronto tractable transactions translating transversals tree trends universal university ussr when width winner yannakakis years
http://doi.acm.org/10.1145/509907.509949	31	On Paging with Locality of Reference	addison algorithms analysis annual behavior belady better borodin cambridge chrobak communications competitive computation computer computers computing deitel denning discrete engineering fiat fifo ieee irani journal karlin locality model multipointer noga online operating paging past present proc program raghavan randomized reference references replacement schieber sciences sets siam software storage study symp symposium system systems than theory transactions virtual wesley with working yaniv
http://doi.acm.org/10.1145/509907.509971	49	The Price of Anarchy is Independent of the Network Topology	academic algorithms allocation analysis annual applied aspects assignment automatic avoiding bandwidth beckmann bounding braess bureau capacity case chammah ciency civil cking communication comp computer computing congestion control cornell czuma dafermos data designing dilemma discrete economics ects edition engineers equilibria erative etitive foundations friedman full game games general generic gross hard harris ieee institute internet journal korilis koutsoupias lazar mathematics mavronicolas mcguire michigan multi multiuser nash national network networking networks nonatomic noncoop operations orda ounds owen pages papadimitriou paradox path pendarakis preparation press price prisoner probability problem proceedings queueing references research road roughgarden routing scheduling science series shimkin siam some sparrow spirakis stackelb standards strategies structures studies symposium tardos tarjan theoretical theory thesis third tight transactions transportation under university user users version virtual volume wardrop wiley winsten working worst yale
http://doi.acm.org/10.1145/509907.510021	89	Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models	acquisition added adding addition advice algorithm algorithms allow already annual appendix approximability approximations arbitrary areas arikawa arrange assume base based both call called cantly case cedure change choice cient claim class codes coding cohn colton communication complete complexity compressed compression computer concatenation condition conference connection consider constant construction consumed contain context copied cosman could cover covering created criwg data decays depth describ dictionary discrete doesn done each earing easy ecomes edit editors efore eight eing either elements elow else ensuring entry equivalent eration erations evident exactly example expands expansion expansions explanation extended extraction factor fall farach figure first following four framework free from future general gives global grammar grammars greedy have hence here heuristic hierarchical higher ieee increases increasing individual inductively inferring information initialized insert instance instead institute interest interesting into introduce issues john journal just kida kolmogorov language larsson last leading leaf least leaves leftmost lehman lemma lemp level line lonardi lossless making manning marcken massachusetts matching mathematics maximum methods model models most multilevel natural neither nelson nevill nish nodes nonterminal nonterminals note numb occurrence occurring oints ones only operations order ossible ostolico other ower owerful pages parameter part partial pattern personal practical practice presumably princeton problem problems proceed process processed processing produce produced proof prove pushed rate real reasonable recursion recursive references relevance remaining replace replacing representation research resp resulting return returned rightmost root rule rules satis scenario sequences sequential shaded shelat shibata shinohara shows side signi simply size smallest snowbird soda some sometimes sons source spanning spans spire start storer string structure study substitution such symb symbol symposium take takeda technology terminal terminals textual that their then theorem theoretically theory there thesis they thirteenth this thomas three total transactions transform tree trees uncomputability unifying universal university unsupervised using utah variable waikato when which whose wiley with within without witten work world would write yang york
http://doi.acm.org/10.1145/509907.509987	62	Resolution Lower Bounds for the Weak Pigeonhole R Principle	about acknowledgment advanced american appear applied arithmetic beame boolean bounded bounds branching buss cafe calculus collaboration complexity computational computer computing conference constant content conversations corol done erence examples feasible finally formula foundations from functional games generalized great haken hard helpful hence icalp ieee improved independence institute intractability journal july june larger lary least lecture length like logic lower made make manuscript matching math mathematics monthly most narrow notes once organizers other papers participants perfect pigeonhole pitassi polynomial presented principle principles proc proceedings programs progress proofs propositional publications pudlak razborov read rectangular references refutation regular research resolution results sasha sasson science section selected short simple simpli small sometimes special springer study super symposium than thank that theorem theoretical theory there things this toni transversal turan urquhart verlag very weak where which wigderson work world would year years
http://doi.acm.org/10.1145/509907.509991	65	Optimal Finger Search Trees in the Pointer Machine	abstract accomplished acta addition algorithms also anderson annual applications applied average balanced bound bounded bounds brodal california case clancy class combine comp complicated computer computing conclusions considered constant control could data date dating degree deletions dept details devising dietz discrete disjoint driscoll dynamic eatcs either enhance erations erts extended fast finally finger fingers fleischer foundations fusions future guaranteed guibas harel however huddleston included informatica information innovative insertion interested international intuition irvine journal known knuth kosara letin letters levcop like linear lists localized long lueker machine maintain making mayb mccreight mechanism mehlhorn movable multiple must nger nonlinear nordic note ointer onent onents operations other oulos overmars pages partially persistent plass priority problem problems proc processing programming queues raman rebalancing references representation representing require rotations sarnak scheduling scheme science sciences search searching seminar sets several siam simple simpler sketched sleator soda solution solving some sorted splits stan standing stanford stoc structure structures surely symposium system tarjan technical technique techniques that theory they this thorup tight time tree trees tsakalidis university update updates using version well were which will with worst would
http://doi.acm.org/10.1145/509907.509940	24	Almost all graphs with average degree 4 are 3-colorable	about above academic account achlioptas adjacent again akad algorithm algorithms allocations allows alon also always american among analogously analyses analysis andom annual another appendix appl applications applied approximation argue arguments assigning asymptotic athreya balanced based because before begins being belonging belongs below bender bernoulli between boettcher bollob bound bounded branching brelaz bucket cannot carnegie case changed choose chooses claim clearly color colorability colored coloring combin combining comes comm communication comput computer computing conceal consider construct construction copies copy core correspond corresponding coupled course creating critical current dangerous decreases degree dependently depends derived determine determined determining diminish distributed distribution distributions divided dominate dominated dominates draw during dynamics each easy ects edge edges electron elsevier emergence entries enumerate enumeration equal equals equation equations erence erential event events every evolution exactly except execution exists expectation expectations expected experiment expose exposed extremal fact fails failure families finally following follows foundations free friedgut frieze from generated geometric giant give given gives governing graph graphs greater guarantee guration hand harder have having heuristics history hits holds identical identically imagine implies indeed independent independently industrial instance interested into john jump just karp kirousis kozl kurtz kutato label labelled lacks least lemma length less lett limits list load london long loop loops lost lower magyar make manner markov matched matchings mathematics matrix maximum mellon method methods miami mitzenmacher mode model models molloy more moreover most multiple multiplied multiplying multitype need never newcastle nition note number observation observe observing occurrence occurring occurs omitted only optimization order ordinary oris other outcome outcomes over pages pair parameter parameters part particular percus perform personal philadelphia phys pick picked pittel plus point population portland positive possibility presence press probab probabilistic probability problems procedure proceed proceeds process processes progenies progenitor progeny property proportional prove publishing pure random rather ratio readily recall recalling reed refer references regard regarding relevant repeatedly respectively rest resulting results rise round same sample science second self selfloops sequence sequences setting several sharp show siam similar similarly simple simply since single sipser smaller society solutions some sons sparse spencer spring square stamatiou standard start starts stealing step stronger structures studying subcritical succeeds success such sudden suen symposium syst take tend term than that their then theory there therefore these thesis third this threshold throughout thus time together total trial trials triv trivial turning type types under unexposed uniformly university value values variable variables vertex vertices wellknown when whenever where which whose wiley will with within work wormald yields york
http://doi.acm.org/10.1145/509907.509970	48	Crawling on web graphs	above absolute achlioptas adler again aiello albert almaden also always american analysis annual appear approximate association assume barabasi being between bollob bounded broder chains chooses chung ciently completes compressing compression computation computer concentration cond conductivity conference connected consider constant context cooper counting counts data deduce degree denotes diameter ding drinea each edges enachescu establish estimated evolution example except expectation explored expression extend extensions fiat foundations free frieze further gatekeeper general generated generation given graph graphs have henzinger heydon http ieee index inequalities information interest interesting jagopalan jeong jerrum jork journal karlin kumar lanl large lemma like maghoul markov massive mcsherry measuring mitzenmacher mixing model models natural nature neighb networks next note number obtain once only other ours positive possible principal probability proceedings process proof proportional provided publications quality questions raghavan random range rapid rapidly references research result riordan scale science search sequence sets should shows sinclair sivakumar size small some spencer spider stata state statistical steady stochastic structure subset such sums suppose symposium synthesis that then there these this tomkins toward uniform unvisited upfal using variables variations vertex vertices very walk walks weight when wide wiener with within world would
http://doi.acm.org/10.1145/509907.509932	18	On the ComplexRty of Matrix Product i	algebraic annals applications arbitrary arithmetic bilinear bound bounded bounds circuits communication complexity comput computational computations computer computing coppersmith depth detrminant dimensional duke eccc eigenvalue electronic elimination fast forms foundations fourier gates gathen gaussian geman golub hopkins ieee jacm johns journal large limit linear loan lokam loquium lower math mathematical matrices matrix methods morgenstern multiplication nissan norm normal note numer optimal pages press probability product progressions proving pudlak random references report rigidity science shpilka silverstein size smallest spectral spectrum strassen symbolic symposium theorem theory tradeo transform university using variation wielandt wigderson winograd wishart with
http://doi.acm.org/10.1145/509907.510011	81	Space-Efficient Approximate Voronoi Diagrams	advantages algorithm algorithms annu applications approx approximate arya aspect balanced body boundaries callahan chan cient clarkson classes closest combining comput computational curse decomposition diagrams dimemsional dimensionality dimensions discrete dudley duncan elds entropy erentiable found geom geometry goodrich high ieee indyk kobourov kosara kushilevitz linear malamatos metric motwani mount multidimensional near nearest neighbor neighbors netanyahu octrees optimal ostrovsky pages peled point potential proc queries rabani range ratio references removing replacement revisited search searching sets siam silverman size some spaces sympos theory towards trees voronoi with
http://doi.acm.org/10.1145/509907.509979	55	Strict Polynomial-time in Simulation and Extraction∗	alternative applications archive argued argument assumption assumptions average barak barrier basic bellare berkeley beyond black blum bounded brassard cambridge canetti case coin commitment complete complexity comput computation computer computing concurrent conference constant construct crypto cryptography cryptology dept dwork eccr eprint essential eurocrypt everything existence feige fiat focs foundations full functions general goldreich goldwasser hard have hiding identity ieee implied indistinguishable information institute interactive international ipping israel jacm jour journal july kahan know knowledge language languages lapidot ledge levin lindell lncs micali minimal models multiple naor ning noninteractive note notes nothing number onthe ostrovsky pages parallel particular party peau perfect phone possession press problems proc proceedings proof proofs protocols pseudorandomness racko random rather record reducibility references report reports resettable resettably round rounds sahai science secure self shamir siam sicomp simulation sound springer stoc systems technical that their theory thesis this tompa tools tossing trivial under university using validity verlag version weizmann wigderson witness woll yield yung zero
http://doi.acm.org/10.1145/509907.509928	15	Improved Decremental Algorithms for Maintaining Transitive Closure and All-pairs Shortest Paths	algorithms almost although analysis annual answering approach arithmetic barrier birkhauser boston breaking chazelle clearly closure cocoon communication comput computation computer concepts conclusion conference connectivity coppersmith decremental deletion demetrescu digraphs directed distance dynamic earlier edge edges employ exact filtering focs following foundations from fully gave given graph graphs greene hence henzinger improved international italiano journal king knuth later leeuwen lncs lying maintained maintaining maintenance mathematics matrix multiplication number occupies open optimal pages pairs paper path paths pose poutre preprocessed private problem problems proceedings progressions query real reduction references required requirement saving scheme science search seen shortest siam space springer symbolic symposium taking that theoretic this thorup through thus time total transitive tree trees trick under update verlag vertex vertices volume weighted weights while winograd with within witness workshop zwick
http://doi.acm.org/10.1145/509907.509964	43	Approximate counting of inversions in a data stream	adaptive addison aggregation algorithm algorithms alon analysis anatomy andersson approximate approximates approximating babai between brin cambridge caprara castro checkers clear combines communication comp complexity computer computing context counting cycle data decompositions detailed diaconis dietz dimacs disarray discr discrete does dwork engine erence ergun estivill eulerian even events exploiting fast feigenbaum focs footrule frequency graham group help henzinger hypertextual ideas independent indexed indexing intersection inversions itai jagopalan jcss jolet kalyanasundaram kannan knuth kumar kushilevitz large least lecture levcopoulos list lists lncs made makes massive math matias maximal measure methods moments morris naor networks nisan number optimal over page parallel pass passes permutations petersson poly press probabilistic probability problem proc programming raghavan randomized rank ranking references registers representation reversals royal rubinfeld scale schnitger search searching seem sequential series siam simple sivakumar small society sorting space spearman spot springer statistical statistics strauss streaming streams subset survey surveys szegedy that theor theorem there these this university uses viswanathan wads wesley when with wood yields
http://doi.acm.org/10.1145/509907.509945	28	Random Sampling and Approximation of MAX-CSP Problems	ability algorithms alon annual approximation arora azuma certain coloring combinatorial comp computing czuma dense discrepancy doerr eared endent fernandez full graphs hard hoku hypergraph icalp instances karger karpinski lncs luczak math osium polynomial press problems proc proceedings random randomized rectangles references satis scheme schemes schoen shapira siam soda sohler springer structures symp system testing theory time variables vega weighted
http://doi.acm.org/10.1145/509907.510006	77	Time-Space Tradeoffs, Multiparty Communication Complexity, and Nearest-Neighbor Problems	above acknowledgements ajtai algorithms allan alon along alto analogously annual applications applied apply april arguments ashok assignment asymmetric atlanta babai barkol based beach beame bestpartition binary bits boolean borodin boston bound bounds branching cary case cell chandra chung classes combining communication complexity computation computational computer computing consider constant construct coordinates corollary criterion data decision determinism diagrams dimensional direction discrete discussions disjoint either elsewhere equal erik fifteenth first follows foundations from furst generators given have helpful hence high hypergraphs ieee industrial ingo investigation jayram journal juan laszlo lemma linear lipton logspace lower maass mario mathematics matt meanders memory merrick michael miltersen model multi multiparty nearest neighbor neight nicholas nisan noam noga note november oblivious obtain october offs only ostrovsky other over pages palo partial party paul pippenger portland probe problem problems proceedings program programs protocol protocols prove pseudorandom puerto quasi rabani rams random randomized randomness razborov read redondo reduction references related required resource respect restrictions richard rico roman safra saks science sciences search second siam simultaneous since size smolensky society solves solving some space structures subsets such suggesting super suppose symposium system szegedy tetali thanks that thathachar their then theorem theory there thirty this thus tighter time times timespace trade tradeoff tradeoffs unassigned versus wegener when wigderson with wolfgang xiaodong york yuval
http://doi.acm.org/10.1145/509907.509985	60	Relations between Average Case Complexity and Approximation Complexity	ability able adding agree ajtai alex algebraic algorithm algorithmica algorithms almost alon american amortized andreas annual appendix applications applied approach approaches approximate approximation arbitrary argument arising assign assigned assignment assignments associate asymptotically attempt average beame bisection bound cantly case catalog characterization check chvatal cient ciently clause clauses close cluases combinatorial compared complete complexity compression computational computer computing conclusions conditions conference consequence consider consistent constraint constraints contradict coordinate coordinates correspond corresponds data david defeating dense derandomized designing dictionaries discrete dodis does dubios each easily economic editors ehud elimination else elsevier enough ensures even every everywhere exactly examples extended extract fact false feige focs following follows formula formulas four friedgut friedman from function generating geordt given gives giving goemans graph grows guassian guest guruswami hard hardness hastad have hence here high hypothesis icalp improved inapproximability inequality inner instances intention involving jacm jection jective joel johan journal karlo karp khanna kleinberg kortsarz krauthgamer krivelevich langberg large lattice leads leighton levin literal literals luca made many matched mathematical maximal maximization maximize maximum methods michael micro mike minimum mining misses mitzenmacher monasson more moreover most multicommodity multiple narrow nding nearly necessarily necessary negated nite notation note number numbered numbers observe optimal optimization order oregon orthogonal other outward pair papadimitriou particular partitioning paso paul peleg phase pitassi polarity polylogarithmic polynomial portland precision present preset probability problem problems proc proceedengs proceedings product products program programming proofs properties query raghavan random recognition recognizing references refute relaxations remark require resolution rest results richard rotations rounding saks same samorodnitsky sasson satis satisfaction satisfy science seen segmentation selma semide semidefinite sets shall share sharp short show siam sicomp sign signi similar simon simple sketch smaller society soda solution solutions solved some something specialized spectral squares stacs stoc subformula subgraph subset such summing surely symposium szemeredi texas than that their them then theorems theoretical theory there these this three thresholds time toni tool transitions trevisan true unit unsatis upper uriel used uses using value variable variables vector vectors veri view volume when where whether which widgerson wigderson will williamson with xhxji zecchina zuckerman zwick
http://doi.acm.org/10.1145/509907.509930	17	On Randomized Online Scheduling	acta adversaries albers algorithm algorithmica algorithms amortized analysis analyze ancient annual anomalies answer appear balanced barely bartal because bell better bound bounds cannot case certain chen chine ciency communications computer computing consider cybernetica desired discrete european faigle fiat fleischer follows galambos games general generating gormley graham have hence heuristic implies information journal karger karlo kern leading letters line list lncs lower more multi multiprocessor next online paging particular performance phillips placed problem problems proc processing rabani random randomized ratio references reingold request revisited rules scenario schedule scheduling sciences seiden sequences setting sgall siam simultanously sleator smallest springer statement study symposium system tarjan technical than that thus torng turan update vliet vohra wahl westbrook which with woeginger worst
http://doi.acm.org/10.1145/509907.509934	20	Fitting Algebraic Curves to Noisy Data	addition algebraic algorithm algorithms analogue analysis appear appears applied approach approximation april areas assumes assumption being berlekamp berlin bernstein beyond block bound budapest canny chelsea cient ciently classical codes combinatorial comm complexity computational computer computing conceivable conclusions constraints constructive correction counterexample counterexamples curve curves cvgip dasgupta data december decoding deductive derivatives describe detect detection devore digital discusses does duda edge edges equal erdelyi erdos error even examination exist exists extremal focs fraction freeman from functions generated generates geometric gives graphics green grotschel hamilton hart have heidelberg here hildreth history hough however hueckel hungary ieee illingworth image indeed inequalities intelligence interest interesting jacm journal july kittler learning least leavers lines lipton locates lond london longman lorentz lovasz machine manuscript many march markov marr math mathematics methods mill mixed mixing mixture nishing nondegenerate number operator opposed optimization pairs pami patent pattern paul pause pavlov perception pessimism phil philosophy pictures polynomial polynomials practice prelim present problem proc processing proof properties really reason reconstructing reconstruction reed references rely royal rubinfeld same schrijver section sections seems selective siam singer solomon springer stated sudan suggest survey that then theories theory thing this time trans transform transformation tried tting type under understanding unrealistic unstructured useful using valiant verlag version vision visual weights welch when which william work york
http://doi.acm.org/10.1145/509907.509933	19	Near-Optimal Sparse Fourier Representations via Sampling	achlioptas advances after algebraic algorithm algorithms alon alto altogether analysis angle annual appl application applications approximate approximating approximation approximations arbitrary areas assess assessing been best boolean cannot cant carlo case cation choose cients circuits communications complexity components comput computation computer computing conclusion consider constant contemporary continuous corresponding data datamining decision denote depth details dictionaries discrepancy discrete donoho easily equations erential error estimate estimation every exact example extensions fact factor fast figure finding focs follows foundations fourier frequencies frequency frieze from function functions gilbert good growing guarantee guha happen have high hilbert histogram identi ieee implications improved independent indyk information input international interpolation into issac iteration iterations jacm january johnson june kaltofen kannan know kotidis kushilevitz learnability learning least lemma length letters lindenstrauss linial lipshitz lipton list lncs main maintenance mallat mansour mapping matching math mathematics matias matrix mcsherry minimizes miss mixed moments monte most multiple multiplying multivariate muthukrishnan near neural nisan noise omit only optimality orlitsky otherwise output over palo poly polynomial polynomials positions possible precision presence principles probability proc proceedings processing proof provide pursuits pythagorean quality rank reconstructing recovery reduced references regard representation residual right ropt roughly roychodhury rubinfeld sample sampling science sets several shannon short show siam signal signi small solution some space sparse speci spike sprectrum springer stark statement still stoc strauss subsequent such sudan suppose symbolic symposium szegedy term that their then theorem theoretical theory these this three thus time transactions transform trees uncertainty unfortunately used using vempala verlag weaver which wiley will with within yagati yields zero zhang
http://doi.acm.org/10.1145/509907.510001	73	Polynomial-Time Quantum Algorithms for Pell’s Equation and the Principal Ideal Problem	abstract advances adxn aives algebraic algorithm algorithmic algorithms almost amer annual ants apply architectures asymptotically august based bernstein bosma brassard buchmann chapter choices cient claim class clay cohen complexity comput computation computational computer computing concerning coset course crete crypto cryptology determination discrete editor elds elian equation ettinger exchange extended factorization fast graduate greece grigni group groups hallgren heraklion hidden html http index instances institute integer introductory inverse island ivanyos john journal july karmarkar knill least lect lecture lenstra linear logarithms lond magniez manuscript math mathematics mechanical minaire modulo msri nombres nonab normal note notes notices numb number olynomial onential oregon orie orthogonal ower pages paral paris pell polynomial portland prime probability problem problems proceedings programming publications quadratic quant quantum real reconstruction reducing references regulators remarks representations rewriting russell sample santha schrijver schulman science second seeing shma shor siam simon since solving some sons springer states subgroup such symposium system technical texts theory therefore third thirteenth thirty time times using vazirani verlag video vollmer volume wiley williams with workshop york
http://doi.acm.org/10.1145/509907.509993	67	Deterministic Sorting in O(n log log n) Time and Linear Space	access addition agerup albers algorithm algorithms aman andersson architectures arrays aspects august boas boolean bound bounds cient closest comput computation computer computing concurrent conference conservative design deterministic dichotomous dietzfelbinger discrete emde european expected fast foundations fredman fusion hagerup hypercubes ieee implementation improved infom information integer integers international introduction jainen kaas kata kaufmann kirkpatrick lecture leighton lett linear machines manuscript mateo math monotone morgan nilsson nonconservative notes ombinatorics omputing operations pair parallel penttonen priority problem proc process publ queue queues raman random randomized references reisch reliable science searching sequential shen shift siam small soda sorting space stacs surpassing symp symposium syst system theoretic theoretical theory thorup time trans trees upper using willard wise with without writing zijlstra
http://doi.acm.org/10.1145/509907.509976	53	Exact learning of DNF formulas using DNF hypotheses	abstract aizenstein algorithm algorithmic algorithms analysis angluin annual applications approximating asking association automata balcazar beimel bergadano berggren bias blum bounds bshouty castro chandra characterizations characterizing cient circuits classes combinatorial complete complexities complexity computation computational computer computing concept conference conquer constant constructions covering dana david depth deterministic dimension dimensions discrete distribution divide domain equivalence equivalent errors ership exact exclusion fast formulae formulas foundations fourier fourteenth free furst general generalized goldman guijarro hancock hardness hegedus hellerstein help ieee implicants inclusion information intl jackson jorge jose journal kearns kharitonov klivans kobler kushilevitz learn learnability learning letters limits lindner linear linial machine machinery mansour manuscript many markowsky masek matar mathematics memb michael minimization minimize minimum mistake models monotone muller multiplicity nader naor nathan needed networks nisan noam numb onential oolean oracles ound over pillaipakkamnatt pitt preparata prime probability problem problems proc proceedings processing prop queries query questions raghavan references resp results rudich science sciences separating servedio shortest siam simple sixth small some sorting spaces statistical stoc switching symposium system tarui teaching term theoretic theory thirteenth time transform tsukiji twenty umans uniform unpublished using varricchio weakly when wilkins with workshop yishay
http://doi.acm.org/10.1145/509907.509996	69	Algorithmic derandomization via complexity theory	ability achlioptas addison algorithm algorithmic algorithmica algorithms alon amazing analysis annual appear appendix applications approach approaches approximate approximating approximation armoni babai based berger berkeley bias bits bounded california cambridge cant cations chor cient coloring combinatorial combinatorica complexity computation computational computer computing conference connectivity constraints constructing construction constructions counting cover covering crypto curse cuts dasgupta data database derandomized derandomizing deterministic dimensionality discrepancy discrete distributions donnell dspace dual easy edition editor elementary embeddings engebretsen extensions fast foundations frankl friendly generators geometric geometry given global goemans goldreich graph graphs gupta hardness hilbert hochbaum ieee improved independence independent indyk integer into inversion itai jagopalan jections johnson journal karger karp knuth koller least lecture lemma lindenstrauss linial lipschitz london luby maehara maha mappings matching mathematics matrix maximal maximum megiddo method modern motwani mulmuley naor nearest neighborhoods neighbors nisan nite notes optimization other packing pages pairwise parallel pods poly power press primal principles probabilistic probability problem problems proc proceedings programming programs proof pseudorandom publishers rabin rabinovich raghavan ramesh rami ramos random randomization randomized randomness reduction references removing report rompel rspace saks sample satis satisfying schulman science sciences secure semide seminumerical series shma siam signi simple simulating sipser small solving some space spaces spencer sphericity springer srinivasan stable stockmeyer stream subrahmanyam sudan symposium system systems szemeredi technical theoretic theory titled towards undirected uniform university using vazirani verlag version volume wesley wigderson wiley williamson wise with yields zhou
http://doi.acm.org/10.1145/509907.509980	56	Universally Composable Two-Party and Multi-party Secure Computation	able adaptive adaptively agreement aiken algorithms applications archive assumption authenticated based beaver berkeley binding blum brassard byzantine cacm california canetti chapter chaum chosen cient ciphertext claim coin cols commitment commitments committing communication comp compcom completeness complexity comput computation computations computer computing concurrent conf congress constanst contracts crep crepeau crypto cryptographic cryptography cryptology damgard decemb desantis details dicrescenzo disclosure dissertation distinghished distributed dolev dwork else encryption eprint eurocrypt even exchange expansion factor fair fault faulty feige feldman fischlin focs full functions galil game garay general generate generators goldreich goldwasser hard harvard have hiding homepage honest html http iacr ieee immoral improved integrity interaction interactive international ipping ishai jacm jcss joint jority journal katz kilian knowledge kushilevitz languages lapidot lemp levin lindell lncs lysyanskaya mackenzie malleable manuscript manuscrtipt mathematicians memo mental micali minimum minority multi multiparty multiple naor nielsen nothing oblivious oratory osable osition ostrovsky pages paradigm party perfect persiano play predicate preliminary presence preservation private probabilistic proceedings proto prove pseudorandom public rabin racko random randomized randomness reactive reducibility references ress richardson robust rogaway rounds sahai santis schemes secret secrets secure security shamir sharing siam signing single smith spring springer state stoc string systems tech telephone that their theorem theorems tolerant tolerating transfer tzmann unconditionally universal universally unpublished uses using validity veri verlag version waidner weizmann wigderson winter wisdom with without yield yung zero
http://doi.acm.org/10.1145/509907.509942	26	Reimer’s Inequality and Tardos’ Conjecture	appl applications appropriately berg berkeley blum cates certi choosing classes comb combinatorica communication comp compl complete complexity comput conf conjecture consequences cult dual efore ercolation ersonal exists expanded expansions focs from fully function functions generic hartmanis have hemachandra ieee impagliazzo independent inequalities inequality initially kahn kesten last leaf limits markov natural nonisomorphism oolean oracle oracles otherwise over pages previous prob probab proc proof provable query random references reimer reliability robustness rudich separate sets show similarly since size smyth struct such summing sums supp tardos that theory there thesis thus tree unexpanded version where with
http://doi.acm.org/10.1145/509907.510022	90	Limits to List Decodability of Linear Codes	able about above acknowledgments actually adjacent again alexander algebraic algorithms almost already also alternate always amit amnon among amsterdam analysis angew annual appealing appear appendix apply approach arbitrary argue argument artin associated assume assuming assumption august away ball based because being believe best between bipartite both bound bounding bounds call cally canceled cannot cantly carefully case cases certain channels chapter checked chinese christopher cient claim claimed classic clear clearly close code codes codewords column columns combinatorial communication completes computer computing concatenated concerned concerning conclude concluding condition conference conjecture consider constant construction constructions contain contains control correcting corresponding corresponds could course cult david deal decision decoding degree deleting denoted design desired details determinant discussions distance distinct distinguish does during each easily edge either electronics element elements elias elsevier elusive emil encourage enough entries entry equation erent error establish evaluate even every exactly exhibit exist exists expansion exponential exponentially extensions extractor fact facts february following follows foundations from function further furthermmre furthermore generality geometric give given gives giving goal goldreich good graph guruswami hall hamming handy have hence here highly holds holdt holland hooley hypothesis ideas identify ieee implies imply improved includes indeed indeterminate indeterminates indexed information instead institute intel into involved involves itself johan john johnson july just justesen known koetter label laboratory lang large last later learning least lected lemma lerton less ligencer like linear linearalgebraic list lled lling long loosely loss lowing lpoly macwilliams made madhu makes making manuscript many massachusetts matches matching math matrix means method minimum more most multilinear murty must ndexed nding necessary neighbor neighborhood neighbors neil niteness noisy nonzero north note ntries number obeys obtained obvious october oded once only open other otherwise outside over pages paper papers partial particular pattern permuting peter pick polynomial polynomials polynomialsmis positions possible precise primitive proceedings prodn product progress proof property prove provided purely quarterly queries question questions radius ralf rank reader reason recall recalled recent recollect reed refer references reine relative relevant remainder remained remaining remains remarks report research result results ronitt roots rough rows rubinfeld sahai satis science sech selmer sets setting shma shorter shortly should show side signi simpler simply since situation size sized slightly sloane soft solomon some somewhat speci springer stad state states step still strictly subcases subgraph submatrices submatrix subset subsets succeed such sudan suggested suggesting suggestive suitably super superpolynomial symposium task tate technical technology tedious term terminology than thank thanks that then theorem theoretic theory there therefore these thesis they this thus together towards transactions tricky ultilinear unconditionally understanding univariate upper used useful using value values vardy variable vectors venkatesan veri verlag vertex viii violated want well were when where which whose will with within without words work would wozencraft zero zeroes zuckerman
http://doi.acm.org/10.1145/509907.510010	80	Computing the Betti Numbers of Arrangements	addison advanced advances agarwal akad algebraic algebriques almost applications applied arrangements automata available balls basu berlin betti bochnak bott bounds brique cairns cambridge cation cell chapter chazelle closed cohomology collins combinatorial complexity computational compute computed computer computing conference contemp coste crucial cylindric data decomp decomposition dimensions discrete dual ectral edelsbrunner edition editors elds elements elimination equal erent erential erties exists focs follow formal forms foundations four from gatech general geometry goodman group groups guibas guide halperin handbook here higher holland homologie homology homomorp homomorphisms horizontal hyperplanes induce induced introduction ious isomorphisms iterate journal journalsocg just koltun languages lecture letscher listed local manifolds maps math mathematics mccleary method milnor mover munkres nauk next north notes numb observation oleinik ological ology onential orary order orlik ositions ounds outlined persistence petrovski phisms piano preliminary press princeton problem problems proc proceedings process prop quanti rank ranks real reelles references resp restriction rotman rourke sack saugata scheme schwartz science second section semi sequence sequences shap sharir simpli single space springer sssr strati studies submitted substantially such surfaces symposium taking techniques terao that then theorem theoretical theory there this thom three tight triangulations trie union univ user varietes varieties vector verlag version vertical wesley with zomorodian zone
http://doi.acm.org/10.1145/509907.509954	35	Approximation Schemes for Preemptive Weighted Flow Time	afrati algorithms analysis annals annual appear applied approximability approximating approximation average balter bampis bansal becchetti bender brucker carnegie chekuri completion complexity computer computing dates discrete dyer formulating foundations gehrke goemans hall harchol ieee implementation improved ipco jain jaraman john journal karger kellerer kenyon khanna lenstra leonardi lncs logist machine machines math mathematics migration milis minimize minimizing muthukrishnan naval nonapproximability online operations optimizers pages parallel performance points power preemptive problem problems proceedings production quart queyranne references relaxation release report research results rinnooy scheduling schemes schroeder schulz science sequencing servers shaheen shmoys siam single skutella smith srpt stage stein stretch supermodular sviridenko symposium systems tautenhahn technical theory time total university various volume weighted wein wiley with without woeginger wolsey york
http://doi.acm.org/10.1145/509907.509917	6	The complexity of choosing an H-colouring (nearly) uniformly at random∗	accuracy algorithm algorithms appear approx approximate associated assume available because between bipartite borgs bounded bounds brightwell calling cambridge cases certain chains chapter chayes coloring colorings colouring colourings combinatorial combinatorics complexity component components computer connected constraint cooper counting degree diaz discrete dismantleable distance distribution dyer each easy editors estimating expressed fast focs follows fpras free frieze from galluccio generality generation goldberg graph graphs greenhill guarantees hard hell home homomorphisms html http hypercubic improved independent independently input instance integrating jects jerrum journal lamb lattice lecture london loop losing markov mathematical mathematics mfcs mixing most nachdiplomvorlesung name note notes number obtain output pages paper parameter parameterized paus phase physics preece press print problem problems proceedings pubs random randomly rapidly recent references relation relative samplebh sampling science selfreducible series serna sets simple society sparse specifying springer structures such survey surveys tetali that then theorem theoretical theory there thilikos this transitions trivial uniform university valiant variation vazirani very vigoda volume walks winkler with without zurich
http://doi.acm.org/10.1145/509907.510023	91	Near-optimal linear-time codes for unique decoding and new list-decodable codes over smaller alphabets	alex alexander algebraic alon amin annual appear areas asymptotically august bangalore barg based beyond binary blokh bound bounds bruck buchmann cascaded cient ciently code codes coding combinatorica complexity computational computer concatenated constructing construction constructions correcting correction cryptography curves daniel david december decodable decoding distance dumer editors edmonds encodable erasure erasures error estimate expander exponents focs forney foundations from generalizations generalized geometric gill gitit good graphs guruswami half handbook hoeholdt holdt holland holographic ieee ilya improved india indyk information informatsii institute january jehoshua joseph journal june justesen katsman linear list lubotzky luby madhu manuscript massachusetts meet michael minimum modular moni moscow multilevel naor nauka nearly nielsen noga north october optimal pages peridachi peter phillips piotr pless polynomial problemy proceedings proofs pseudo ramanujan random rasmus rate recil recovery reed references related ronny roth ruckenstein russian sarnak science serge shen shokrollahi sipser software solomon spielman stichtenoth sudan symposium tapia technology that their theoretical theory thesis through time transactions tsfasman vegas venkatesan victor vladut volume wasserman with zhong zyablov
http://doi.acm.org/10.1145/509907.509911	1	Dynamic Subgraph Connectivity with Geometric Applications	advances agarwal algorithm algorithmica algorithms alon applications arithmetic aronov asano barrier bentley biconnectivity binary breaking cates cation certi chan chazelle clique closure compactly component components compression comput computational computing connected connectivity coppersmith cormen counting cycles data decomposable decremental demetrescu deterministic discrete dobkin dynamic dynamically edge eppstein erickson euclidean extrema feder finding forests found frederickson frigioni fully functions galil geom geometric geometry given goodman graph graphs hall henzinger hershberger hill holm hypercubes ieee imai intersection introduction italiano khanna kinetic king kreveld leiserson length lichtenberg line logarithmic lookahead lopez maintaining maintenance matrix maximum mcgraw measures minimum motwani mulmuley multiplication near nissenzweig online operation optima optimal pages partitions planar plane pollack poly polygon polylogarithmic prentice preparata press problems proc progressions randomized range rectangles references relatives represented rivest saxe searching segments semi shamos siam simpli spanning sparisi speeding springer static stein structures suri switching symbolic sympos technique theory thorup through thurimella time trans transformation transitive tree trees updating verlag vertices visibility width wilson winograd with yuster zwick
http://doi.acm.org/10.1145/509907.509965	44	Similarity Estimation Techniques from Rounding Algorithms	ability aggregate algorithm algorithmic algorithms alon analysis application applications approximate approximately approximating approximation arbitrary arpa associations bartal based boolean bounds broder calinescu callaghan cation charikar chekuri chen cient class classi clustering cohen color combinatorica compass complexity compression computation computations computer conf conference connectivity constant containment corner counting curse cybernetics data database databases datar dept derandomized detection dimacs dimensional dimensionality dimensions distance distributions documents donnell duplicate earth eddings edge eling endent engebretsen erator ermutations estimation euclidean expansive extension factor family fast fields filtering finding focs formulation frequency frieze fujiwara functions generators gibb gilb gionis glassman goemans guha guibas gunopulos gupta hash hashing haveliwala high histogram icde ieee image images improved indep indyk information interesting international intnl invariance jacm jagadish jcss join karlo khanna kleinb korn kotidis koudas krauthgamer limited linear linial locality lower maintenance manasse markov massive matches matias maximum metric metrics mishra mitzenmacher moments motwani mover multi multidimensional muthukrishnan naor navigation near nearest neighb network nisan nite novemb ounded pages pairwise pass pattern perceptual pods preserving probabilistic problem problems proc proceedings programming pruning pseudorandom queries quick quicksand rabani raghavan random recognition reduction references relationships removing resemblance retrieval rubner ruzon sasson satis scalable scaling science search selectivity self semide sequences sets sigmod similar similarity sizes small society soda space spaces srivastava stable stan stanford stoc storage strauss stream streams structures summaries summary supp synopsis syntactic systems szegedy tardos tech technical techniques texture textured these thesis tomasi towards tracking transformation translation tree tunable twig ullman under understanding university using vempala vision vldb wavelets webdb wide williamson wise with without workshop world yang zosin zweig
http://doi.acm.org/10.1145/509907.510007	78	On communication over an entanglement-assisted quantum channel	access ambainis annual automata bennett berkeley bernstein bounds buhrman california cambridge channels chuang circuit classical cleve codes communication communications complexity computation computational computer computing conference cover disjointness dual einstein elements entanglement erators estimates foundations function hayden holevo ieee information inner interaction international john journal jozsa klauck kushilevitz lecture letters lower manuscript nasa nayak nielsen nisan notes olynomials oneand onential optimal orting ounds pages particle peres physical podolsky press probabilistic problems proceedings product protocols quantum random references review rosen sampling schulman science separation series shma shor siam some sons state states symposium tapp telecommunications telep theory thesis thomas transactions transformations transmission transmitted university unknown vazirani vegas volume wiesner wigderson wiley wolf wootters york zuckerman
http://doi.acm.org/10.1145/509907.509946	29	A Polynomial-time Algorithm to Approximately Count Contingency Tables when the Number of Rows is ∗ Constant	aldous algorithm algorithms annals annual application applications approach approximate approximating approximation arrays berlin bodies boston bounds carlo carnegie chain chains chung column computer computing contingency convex coste counting department diaconis dies discrete discussion dyer efron endence enumeration frieze gangolli generation graduate graham greenhill hard harvard hernek hochbaum improved indep integral integration international interpretations jerrum journal kannan karp kelley lecture luby margins markov mathematics measure mellon metho monte morris mount notes optimization polynomial press probability problems proceedings random randomization rectangular references reliability report rowed salo sampling science simonovits sinclair spencer springer square srinivasan statistic statistics steele structures sums symposium table tables technical techniques testing texts theoretical theory thesis time university varaiya verlag volume volumes walk walks with workshop york
http://doi.acm.org/10.1145/509907.510020	88	Huffman Coding with Unequal Letter Costs	abraham abrahams addison algorithm algorithms alphabetic altenkamp analyses annual applications april arbitrary association automata berger binary blachman bradford capocelli channel channels characterization choi cient code codes coding cohen combinatorics communications complexity computer computing conference constructing construction contr control cost costs cott csisz data december department dependent dept design dichotomous digits direction discrete dolev donald doris duration dynamic edward eighteenth encoding ended ending energy environment equal equiprobable european even foundations free games garey generation gilbert golin good graph guessing hidden hinderer icalp ieee immink infocom inform information international itai january joint journal julia july june kapoor karp knuth korach krause kurt languages larmore lempel length letter letters lncs lopsided loquium lossless machinery march marcus martin mass mehlhorn melhorn memoryless method minimum mobile monge morse nearly ngan noiseless norbert november optimal optimization optimum pages parse parsing perl persiano pgit probabilies probability problem proc programming proofs property publishers raymond redundancy references reingold richard rote rytter sanjiv santis saving science search searching september shannon shimon siam silence simple sixth societies some sorting sound source southeast stanfel stanford storage structures symbol symposium systems theorems theory thesis toby trans transactions transmit tree trees unequal uniformly university using variable varn volume wesley which with word words yeung young yukelson
http://doi.acm.org/10.1145/509907.510000	72	Secure Multi-party Quantum Computation	able abstract achieving aharonov amme arbitrary available awerbuch beaver bennett brassard cambridge canetti chau chaum chicago chor chuang cient city classical cleve codes communications comp completeness complexity composable composition computation computations computer computing constant correcting cramer crypto cryptographic damg dishonest distances distributed distribution dziembowski editor editors error eurocrypt extended fair fault faults faulty feigenbaum focs foundations functions game general goldreich goldwasser gottesman half hirt honest iacr ieee illinois immoral information integrity interactive jority june knill letters levin lncs long march master menezes mental micali minority multi multiparty nielsen oregon over pages paradigm party peau physical play portland preliminary presence preservation press proc processors protocols quant quantum rabin rate reactive references review rogaway science seattle secret secure security share sharing siam simultaneity smith springer stern stoc submitted systems theorem theorems theory thesis tolerant tolerating tradeo tzmann unconditional unconditionally universally university unpublished vanstone veri verlag version volume waidner washington wigderson with work york
http://doi.acm.org/10.1145/509907.509977	54	Monotonicity testing over general poset domains	academy algorithms alon america analysis annals annual appear appeared applications applied approximation arithmetic association available batu behrend belmont bolyai bounded bounds branching bulletin carrying characterization checkers cient codes colloquia column combinatorica communication comparisons complexity computational computer computing conference connection constant contain cornell czumaj decisions decomposition degree dilworth dodis durrett duxbury eccc edition ergun european examples fast fischer functions geometry goldreich goldwasser graph graphs handbook hastad have ieee improved informacii integers international janos journal kannan kluwer krivelevich kumar languages large learning lehman levenste linearity lipton manuscript master math mathematica mathematics matrix meshulam method monotonicity multidimensional national necessarily newman nternational number ordered packing pardalos partially pcps peredaci personal planar points polynomials preliminary press primer probabilistic probability problems problemy proc proceedings program programs progression properties property queries rajasekaran randomization randomized raskhodnikova read references regular reif report robust rolim rubinfeld russian ruzsa samorodnitsky science sciences second separator sets siam simple societatis sohler spencer spot states stoc strength sudan symposium system systems szegedy szemeredi tarjan technical techniques terms testable testing tests that theorem theoretical theory thesis three triangles triple tutorial twice uninformed united university upper vectors version viswanathan weight which white width wigderson wiley with workshop york ziegler
http://doi.acm.org/10.1145/509907.509936	21	A new average case analysis for completion time scheduling	abramowitz algorithms analysis annals annual applications applied approximation automatique based computer computing constraints cont contributions cost deadlines deterministic discrete dover econ ected editors erformance erwolfach feller foundations functions general gilb glazebrook graham handbook hofri hring identical informatique inria institut introduction jobs john journal karmakar lawler lect lenstra list logistics loss machines management mann math mathematical mathematics mcnaughton minimize model national naval notes olicies onential oper operations optimality optimization optimizers ordered ower owtime packing pages papadimitriou parallel pinedo precedence precendence priority probabilistic probability problems proceedings processing processors production publications quaterly radermacher random recherche references relative research rinnoy rothkopf rules sanlaville scheduling schulz science sequencing service siam single smith some sons stage static stegun stochastic stochastically strategies survey symposium syst tasks technical theory times tree tsitsiklis uetz varaiya variable various volume walrand weiss wiley with york
http://doi.acm.org/10.1145/509907.509986	61	Vertex Cover on 4-regular Hyper-graphs is Hard to Approximate Within 2 − J	absolute acceptance algorithms analyze annual appendix approximability approximate approximating approximation arising arora assume beach before being bellare below biased bits both bound bounded bounds bsolute california case cation characterization checking classes clauses cliques colloquium coloring combinatorial combining communication complexity comput computational computer computing consider constant corollary correspond corresponding cover crete degree dinur discrete disjoint each electronic element eleventh empty equality error expression factor factors feige feinberg first following follows foundations francisco free from furthermore generality generalization gets goldreich goldwasser graduate graph graphs greater guruswami halperin hand hard hardness have helps hence hersonissos holmerin hyper hypergraph hypergraphs ieee importance improved inapproximability inserting instances institute interactive intersection interval johnson july june khot langberg large least left lemma lemmas location loss lund manuscript master maximization most motwani need next ninth optimal optimization other over pages papadimitriou parallel parseval partitioning paso pcps personal petrank picking picks portional possible probabilistic probability problem problems proceedings prod proof proofs proportional protocol prove prover provers quantity random reasoning receiving redondo references regular repetition report restricted results returns round safra same school science seen selects several siam side similarly since size small some stad strategy success such sudan sums symposium syst szegedy technical term terms test texas than that then theorem theory there these thesis third thirty this threshold thus tight towards trevisan twenty uniform unlikely used value values veri vertex want weizmann when where which will with within without yannakakis
http://doi.acm.org/10.1145/509907.510017	86	On the Power of Unique 2-Prover 1-Round Games	algorihmica algorithms almost alon along also amortized andersson annual appendix applications approximability approximate approximating approximation arora assign assignment assignments assigns assumption aviv behind being bellare biased bisection bits boolean bound bourgain cation characterization checking clique colloquium coloring complexity compo component computational computer computing constraint constraints corresponding cover dinur directed direction directions discrete distributed distribution dual effort electronic emma engebretsen equations error except exist fact feige finding following follows foundations fourier free frieze from function functions given goemans goldreich guruswami hard hardness hastad have hence however hypergraph hypothesis ieee implies imply implying importance improved inapproximability independence index inequality institute into intuition involving israel jerrum journal kahale kann khanna khot klein lagergren least lemma lemmas linear lovasz lund magnitude manner manuscript maximized maximizes most motawani multicuts nent nents nishing nite number objective optimal pages pair panconesi parallel part pcps plotkin possibly power probabilistic probability problems proc procedure proceed programming proof proofs protocol prove prover query range reduction references repetition report results rigorous round rounding rsults safra samorodnitsky satis satisfaction satisfying science second seen semide several show siam simple simplicity since solution some speci spectrum spherically stad standard state statement steiner substituting such sudan sume symmetric symposium systems szegedy take takes tardos technical technology that their then theorem theory there this three threshold thth thus translate trevisan trivial under union unit university unpublished useful using value variables vector vectors veri weizmann where which will williamson with within would zwick
http://doi.acm.org/10.1145/509907.509972	50	Combinatorial Logarithmic Approximation Algorithm for Directed Telephone Broadcast Problem	acknowledgements algorithm algorithms alon also annual approach approx approximating approximation assoc august author between blum boston bound bounded broadcast broadcasting cation colorable coloring combinatorial communication company complexity comput computer computing david designing determinism discrete discussions disjoint distance distributed dodis dorit edited european explaining exponential focs foundations fraigniaud gaber goldberg goldreich gossiping graphs grateful guha hard hardness hedetniemi helpful heterogeneous hochbaum ieee inapproximability information international itai journal karger khanna kortsarz langberg letters liestman linial lncs lotker lower lund mach mansour maximum methods michael minimization minimum mode motivating multicasting naor networks optimization pages pairwise parallel paths peleg principles private problem problems proc processing publishing radio rami randomization rapid ravi reduction references repetition rumor schieber schindelhauer science sciences siam spanners survey symp system tarjan thank theorem theory time under vertex wishes with workshop yannakakis yehuda zvika
http://doi.acm.org/10.1145/509907.509959	39	O Concurrent Zero-Knowledge With Timing, Revisited	application arguments authors auxiliary available barak barrier based basic bellare beyond black bounds brassard cambridge canetti chaum cient commitment complexity composition computationally computer concurrent constant constraints construct convincing crepeau crypto cryptography damgard date disclosure does dolev dwork eccc encryption error eurocrypt february feige focs foundation from full function functions generator generators goldreich goldwasser hastad have icalp impagliazzo interactive internet jacm jakobsson jcss kahan kilian knowledge krawczyk languages levin lindell lncs logarithmic lower luby malleable micali minimum model naor need nitions nothing optimal oren pages parallel perfect petrank poly preliminary preparation press probabilistic proof proofs properties protocols pseudorandom racko reducing references repetition requires resettable revisited richardson rosen round rounds sahai science shamir sicomp simulation sound springer stoc string systems tentative that their theoretical theory this timing title tools trapdoor university using validity verlag version versions wigderson with yield yung zero
http://doi.acm.org/10.1145/509907.510016	85	3-MANIFOLD KNOT GENUS is NP-complete ∗	ability achen acta advances agol algorithm algorithms annalen bestimmung chichester closed complete completeness complexity computational computers computing decide decomposition decompositions dehn dreidimensional dreidimensionalen equivariant francisco freeman garey genus geschlecht geschlossene guide haken hass integer intractability invariant isotopiekriterium jaco jahresbericht john johnson journal kneser knot knoten kreisknoten lagarias linear link linois manifold manifolds mannigfaltigkeiten math normal oertel pages pippenger preparation primfaktorzerlegung problems proc programming raumes references rubinstein satis schaefer schrijver schubert seifert sons surgery symp theorie theory thurston tollefson topologie topology uber verein verkettungen wiley zeitschr
http://doi.acm.org/10.1145/509907.509999	71	Quantum Lower Bound for the Collision Problem	acceptance advances algorithm algorithms also ambainis analogous analogously analogy analysis apart appendix applied apply approximates approximation approximations argument arguments arlington arxiv assume assumption attained available bakhtiari banaszek beals bennett bernstein boolean brassard buhrman calculate calculated call cases cheney cherno choose ciently cients cleve close collision column combined comparison complete complexity computation computational computer computing conference consider constant could crew cryptographic cryptology damg database decision degree department deviate direction directions disadvantage discrete distinct distinctness distinguish distinguishing distribution divides draw durr each eared ecause eccc ecome efore ehlich electronic element elements elian endently equivalent erasing erqnasilattice erties ettinger etween eurocrypt even every exists factorization fast finally first focs following follows form former foundation free from functions gitterpunkten given grigni groups grover hand hash have heiligman hence here hidden hill idea ideas ieee implies improve increases indep information input inputs integer integers interval introduction jersey journal july kashe kent kitaev knowledge large latter least lecture lemma linearly lines logarithms loquium lower magniez manipulating manuscript march mathematics mathematische mcgraw measurements measures mechanical minsky more mosca most multilinear multiplicities murray must naini national need news next nisan nite nonab noncommutative note notes numerical obtain octob oint oints olynomial olynomials oneto only optimized oracle oracles other otherwise ound ounds over ower pages pairs parameter perceptrons pieprzyk point polynomen polynomial prams press prime probabilities probability problem problems proceedings product promise proof proofs prop public pubs putting quadratic quadratically quant quantum quasilattice rains random range rather real references remainder returns rivlin roughly safavi sahai same santha schemes schulman schwankung science sciences search section separation sequences setcompn sets shor show siam sigact signature similarly simon since size sketch solution some sparse springer stabilizer standard statistical stoc strengths subgroup subgroups subset succinct such super supp survey system szegedy take talk tapp technical tell than that then theorem theoretical theory there thereof though thus time together total tree trees trivariate uicklt uniform uniformly univariate university using vadhan variables vazirani vedral verlag version volume watrous weakens weaknesses what when where which with within wolf wollongong workshop would zeitschrift zeller zero zwischen
http://doi.acm.org/10.1145/509907.509947	30	Approximate Clustering via Core-Sets	ability after agarwal algorithm algorithmic algorithms alon already among angle angles angular annu appear applications approach approximate approximately approximation approximationg arbitrary arora assume believe berlin bern between call cardinality cation check checking cient classi clearly clustering combinatorial combinatorics company comput compute computer conclusions cone cones constructible construction convex core correspondence corresponds cost cylinder decision depending derandomized different dimensional dimensionality direction directions discrete distance distortion doing donnell duda each ection edition editor embeddings endpoint endpoints engebretsen enumerate enumerating eppstein euclidean exact exclusively exist existence extend fast focus found foundations from generated geometric goel gonzalez grotschel guess guessing hard hart heidelberg high hochbaum however ieee image indyk input instance intercluster interesting interscience intersection into know known lemma line linearization lovasz manuscript mapping maximum median might minimize minimizes mishra most motion nding need nite nonempty note number oblinger obviously optimization ostrovsky other over pages paper parnas particular partition pass passes pattern peled pitt point points polynomial precision presented problem problems proc procopiuc programming projection proximity publishing purpose rabani raghavan random rays reduction reductions references related relied remains replace right schemes schrijver science separated separating sets several shape siam since small soda solution solutions solve solved solving space spaces springer step stork sublinear such sulting symp sympos techniques testing that their theoret theory there this thorup those through thus time tting tutorial useful using varadarajan vector verlag version very volume want where which wiley with within would york
http://doi.acm.org/10.1145/509907.509918	7	Random Sampling in Residual Graphs	achieve algorithm algorithmica algorithms always annual another appeared apply approach approximate associate associated augmenting barrier benczur better beyond bipartite bound canadian capacity cates certi choose component components computer computing conclusion connected connectivity course crossing cuts decomposition design deterministic directed discrete distinct each edge edges editor even every fail faster finding flow flows ford foundations from fulkerson galil give goldberg graph graphs have hope ibaraki ieee journal july karger karloff levine linear matching mathematics maximal maximum mincut minimum most much nagamochi natural nding necessarily need network networks node only open operations original over pages path paths perhaps point ponent portions possible preliminary press probability problem problems proceedings progress quantity question random randomized references research residual result same sampling science seems shorter showed shown siam simple since small society soda some spanning sparse stein still stoc stopping strength strong subgraphs such summing symposium tarjan testing than that them then theorem theory there therefore thing this through thus time uire uncapacitated undirected unit using values version well whether while with would york
http://doi.acm.org/10.1145/509907.509963	42	Space lower bounds for distance approximation in the data stream model	above achieved algorithm alon appear approximate approximating arguments averaging babai balasubramanian bounds cambridge case classes communication complexity computation computational computer conference consecutive contemporary convolution cover data disjointness distributed distributions elements embeddings erence estimate extensions eyal feigenbaum first focs following fong fourier frankl frequency function generators georg gives have hilbert identity ieee indyk information intersection into janos jayram jessica joan john johnson kalyanasundaram kannan kumar kushilevitz lemma lindenstrauss lipshitz lower mahesh mapping mario martin massive mathematics matias maxix methods moments nisan noam noga numbers observe otherwise over parseval personal peter piotr preliminary press probabilistic proc proceedings proof pseudorandom ravi razborov references sampath satis schnitger science simon sivakumar size sons space stable stacs stoc strauss stream streams structure subset szegedy that then theoretical theory therefore thomas transform transformation university value version viswanathan weight when where wiley yossef yossi
http://doi.acm.org/10.1145/509907.509958	38	2-Round Zero Knowledge and Proof Auditors	academic adleman ajtai almaden almost applications assumptions auditors banks bounds certi cient combatting communication complexity composition comput computation concurrent constant constraints construct crypto cryptosystem data decryption dertouzos dwork eliminating encryption erez errors eurocrypt feige focs foundations general goldreich goldwasser halevi hiding homomorphisms html http impagliazzo indistinguishable interactive internet junk kahan kilian knowledge krawczyk lncs lower mail micali naor need note pages people personal petrank press pricing primes privacy probabilistic processing proof proofs protocols publications quickly racko reducing references reingold resettable richardson rivest rosen round rounds sahai secure shamir siam springer stoc stock stockmeyer syst system systems technion their timing verlag with witness zaps zebra zero
http://doi.acm.org/10.1145/509907.509968	46	Stability of Load Balancing Algorithms in Dynamic Adversarial Systems	adaptive adversarial aiello algorithm algorithmic algorithmica algorithms analyses analysis andrews applications approximate approximation architectures assignment asynchronous awerbuch balancing balter berenbrink borodin brinkmann bursty combinatorial combinatorica commodity comp computer computing conf contention control crovella designing distributed distribution dynamic eager engineering erformance etitive fernandez ford foundations fulkerson gamarnik geometry ghosh graphs greedy harchol heide homogeneous hurson ieee improved improving jaraman kavi kleinb kushilevitz lazowska leighton linial load local london maggs math maximal measurement meyer mitzenmacher model modeling multi multicommodity murta muthukrishnan network networks oesterdiekho olicies operations ostrovsky packet paral peleg plaxton press problem proc proof protocols queueing rabinovich raghavan randomized references research resolution results richa routing scheduling scheideler schemes science seymour sharing shirazi short siam sigmetrics simple society software some stability strategies strongly sudan symp system systems tarjan task their theorem theorems theory through tight token transactions unbalancing universal upfal wanka williamson zahorjan zuckerman
http://doi.acm.org/10.1145/509907.509952	34	Selfish Traffic Allocation for Server Farms	above achieve adaption additional additionally after algorithms allocation allocations also amount analysis andom appendix applied apply applying arbitrarily arbitrary area argue argument arguments arndt aspects assign assigned assigning assume assuming assumption assumptions automatic average averaging avoiding bandwidth bandwidths basically because beckmann bestavros between biggest blowing both bound bounded bounds braess break called cambridge cannot capacity case causes change chichester choice chosen cient civil claim clearly communication competitive completes complexity computer conclude condition conditions conference consem consequence consequently consider construction continuity contradiction contradicts control coordiassigned coordination corresponding corresponds cost costs crovella czumaj data december denote denoted described describing designing deterministically deviate different directly discussion disjoint dmpletes done douglis down dynamics each easily easy economics economimices edition engineers enough equal equilibria equilibrium equivalent estimate even events every evidence exactly exceed exist existence exists expectation expected fact factor failure family farm fast fastest feldmann finally first floyd focs follow following follows frac fractional frank franken friedman from function functions furthermore game games generality generic gilbert give given gives greater gross guaranteed guarantees hand hard harris have having hence hoeffding holds however huang identical ieee immediately impact implies incentive indeed inequality initial injected instance institution integer international internet into introduction ithat john journal just kleinrock konig korilis koutsoupias krishnamurthy large larger largest last latency later lazar least lemma lemmas linear linearity live lled load loads loss lower made manuscript mathematical mavronicolas maximum maxj mcguire metrics minimizes minimum model modeling mogul monotone monotonicity more moreover most motwani multi multiuser must nash nation necessary needs negation negations network networking networks nish nite nition noncooperative nondecreasing none nonincreasing notice number objective objectives observations observe observing obtain obtained obvi obviously only optimal optimum orda other otherwise ourbinstance ously over pairwise papadimitriou paradox park part particular path paxson penderakis personal pick planation plug point poisson positive possible press prevalence price probabilities probability problem proc proceed processes programming proof properties property protocols prove proves provided pure purpose quence queue queueing queues raghavan random randomized rate ratio rationality recall receives reduced references relationship remaining remains research road role roughgarden routing same satis satisfying scaling scheduling schmidt science scientist second self servej server servers shimkin show shows siam sigcomm similar similarity similarly simple since single situai size sizes slightly slow slowed slowing small smaller soda solution some sons space speci spirakis split stackelberg stacs standard statements steinberg still stoc straightforward strategies strategy stream streams strictly studies study such super suppose symposium system systems taking tardos technologies terms than that their them then theorem theorems theoretical theory there therefore these third this thus tight times tion tional total towards traf transactions transport transportation true tutorial unbounded under unfair university upper usenix user users using value values variability variable variables vector virtual vocking volume want wardrop weight well where whereas which while wide wiley will willinger winston with without works world worst would yale yannakakis yields york zangwill
http://doi.acm.org/10.1145/509907.509913	3	Combinatorial Optimization Problems in Self-Assembly	abelson ability academy adleman algorithm algorithmic algorithms allen american amorphous annual article assembled assemblies assembling assembly based biomolecular breen california cambridge capillary chemical cheng christopher combinatorial communication communications complexity computation computational compute computer computers computing convergence cook coore copyright corrected crossover crystals department design dimacs dimensional dimensions directed discrete doklady edition editors electrical entropy equilibria experiments forces forming geometric goel gomez gracias grotschel growth hanson homsy huang institute isbn journal june kelly kempe khachian knight labean lagoudakis lateral linear local logical lopez lopinski loss louth lovasz machines mathematical mathematics mathias meeting meng mitzenmacher molecular molecules monolayer nagpal nano nanochemistry nanostructures nanotechnology national nature networks optimization organic pages parallel pasadena pattern pennsylvania personal polynomial preece princeton proceedings program programming proving published rates rauch recognition references reif report rothemund rubin running satis schrijver science sciences second seeman self september series seto silicon size society some southern soviet springer squares stoc stoddart strategy structures sussman symposium synthesis systems technical technology theorems theoretical theory thesis third three tien time towards transistors triple universal university unpublished using verlag volume wang wasserman wayner weiss wenzler whitesides winfree wolkow workshop yang
http://doi.acm.org/10.1145/509907.510013	83	Finding Nearest Neighbors in Growth-restricted Metrics	above accessing advances after algorithm algorithms already also among appears appendix applications arranged assignments associative assume augment baeza balakrishnan ball because before behind bentley between binary bound brin called candidate cannot chavez choices chord circle claimed clarkson clear closer closest collapses communications computational computed computing considered consisting constant construction contains copies correctness correspond data december dimensionality directly discrete distance distributed does done each easier element elements encounter enough enumeration environment estimate event events every execute expansion expected factor failure focus followed following follows framework from further general geometric geometrically geometry give global grows growth guarantee half hand happen have here high hold holds however imagine implies include included includes increase increases inequalities inequality information inserted inserting interleaved internet into iteration just karger kasshoek langford large later least lemma less letters lines list lists local logn lookup loop lower manifold many mapping marroqu mathematical median metric more morris most much multidimensional multiplying must navarro near nearby nearest need neighbor neighbors neural nger node none nonlinear notational note notice number objects observations obtain occur only optimal order ordering other output overcomes pages peer perceptual places plaxton point pointers points polynomially possible press previous probability problem problems procedure proceed proceedings processing property prove proximity queries rajaraman random range rank rate recall reduction refer references remains repetitions replicated reports requires returned returning returns richa routine running sampling satis satisfying scalable science search searching second section seeing sense service sets show shows sigcomm silva similarity simplicity since size small soda software spaces stoica structure structures such summarized surveys systems take takes tenenbaum than that their them then theory there these they this thus time times transactions trees true uhlmann unconditionally upper used useful uses using valid value vldb volume ways weide which while will with words would yates yianilos