http://www.informatik.uni-trier.de/~ley/db/conf/stoc/stoc2000.html
STOC 2000
http://doi.acm.org/10.1145/335305.335343	36	On the Complexity of Verifiable Secret Sharing and Multiparty Computation	abstract access achieving addition adversaries adversary against agreement arguments assume available awerbuch beimel bits broadcast build byzantine channel chaum chor cient commitment committer communications complete completeness complexity computation computations computing construction covers cramer cryptographic cryptology damg damggtrd dealt decide decision disc dishonest distributed distribution dziembowski each effi efficiency efficient error eurocrypt extended fault faults fitzi focs follows free from further game general gennaro given gives globecom goldreich goldwasser haifa have here hirt honest however ieee institute journal june karchmer kilian known linear lncs majority massachusetts maurer membership mental micali minority model multi multiparty naor natural ness nishizeki note ones open paper party peau perfect play player plus podc polynomially possible practice precisely presence press private probability problems proc procedure programs proofs protocols pseudorandomness rabin random realizing references related requires saito scheme schemes secret secure sends sets shamir share shares sharing simulated simulation simultaneity situation sketch span springer stoc structure structures subshares such technion technology that then theorem theorems theory thesis this three thus tokyo tolerant unconditionally used using verifiable verlag where wigderson with works zero
http://doi.acm.org/10.1145/335305.335334	26	Resettable Zero-Knowledge*	ability also application august auxiliary available bellare brar brary brassard burocrypt canetti commitment composition computational concurrent crdpeau crypt cryptograph cryptographll cryptography cryptolojy crypts damg disclosure easy eccc efficient eurocrypt focs from full functions generators goldreich goldwasser html http information interactive jcss jour june kilian knowledge library micali model naor pages philby pomps possession practice proofs pseudorandom record reducibility references richardson self settable springer string theopy theory trapdoor ucsd using version well zero zeroknowledge
http://doi.acm.org/10.1145/335305.335327	20	List Decoding Algorithms for certain Concatenated Codes	about above actually agree algebraic algebraicgeometric algorithm allerton alon along alphabet also among amsterdam annual appears arbitrary artinschreier associate associated assume assumptions asymptotically attaining august based below better beyond binary blocklength bound bounds bruck case certain chap chapter check choose claim class code codes codewords coefficient communication comparable complexity component computation computational computer computing concatenated conclude conference consider construction constructive contribution control coordinates corollary correcting correction corresponding curves decoding define defined definition degradation degree delsarte denoted denotes description designed details dfinfeldvladut diameter differ differs dimensional discrete dist distance distinct distribution distributions domain dual each easier eccc elementary elements elsewhere embedding equality equals erased error evaluations even every exactly example except expanded expansion explicitly exponentially extensions fact family field fields find first focs focus follow following follows form formally forney found foundations fourier fraction from function functions further garcia generalized generators geometric give given gives goldreich good graphs grawtchouk guruswamiand hadamard halevi handled have hence here highly hirasawa hold holds holland identities identity ieee implemented implies imply improved include inequalities inform information ings inner input integer integers inventiones journal justesen juxtaposing kasahara kissing kiwi kotter krawtchouk kumar large last ldist learning lemma less linear lines lipton list macwilliams macwilliamssloane manin manuscript many math mathematicae mathematics maximum mceliece mceliecerodemich membership mial minimum modular more most nachrichten namekawa naor need negative noisy normalizing north note number numbers obtained obvious october oist olkp only operations order orthogonal output over packings pairs pairwise parameter parameters parseval partial performance performed personal petrank philips pick places points poles poly polynomial polynomially polynomials polynon position positions preliminary present presented problem proc proceed proceedings product programming projections proof proofs properties proposition prove provided pseudo pseudorandom qdimensional quantity queries random rate rational ravi real reals reconstruction recurs reducibilities reed references rely remark report reports respect result results rodemich roth rubinfeld rumsey satisfies science section sense sets shimura shown similarly simply since sivakumar sloane soft solomon solutions solved soviet space specific squares standard stated statement states step stichtenoth stoc string such sudan sugiyama superimposed suppose symbols symposium take takes technical techniques testing than that their them then theorem theory there therefore these this though through thus tight time together tolerance tower trans transactions transforms treating trevisan trick tsfasman tuple underlying unit unrestricted upper used uses usual vadhan values vardy varshamovgilbert vector vectors version very view viewing vladut weight weighted weights welch weldon when whenever where which will with without works zeroes zink zyablov
http://doi.acm.org/10.1145/335305.335313	7	Isomorphism testing for embeddable graphs through definability	algebraic algebras algorithm algorithms annual approach arbitrary average babai babal beeri bodlaender boppana bound bounded bulletin buneman canonical canonization case cellular chandra characterized chromatic classes closed combinatorica combinatorics complexity computation computations computer computing conference contractible contraction control database databases definability defined describing descriptive determining dimensional distinguishable does done draw ebbinghaus edition editor editors eigenvalue electronic embeddable embedding erdss evdokimov exponential filotti finite first fixed flum foundations fundamentals gcseg generalization genus graph graphs grigoryev grohe group harel hastad have here hierarchy high highly hoffmann hopcroft identification ieee immerman index information inst interactive international invariant irer isomorphism itself journal just karpinski labelling lander lecture lehman lemma leningrad letters lichtenstein linear logic logics lomi london lower luks marifio mathematical mayer means miller model moderately mohar mount multiplicity nauchn ning notes number optimal order otdel pages pairwise paper parameters partial planar plane plenum point polynomial ponomarenko press problem proceedings processing projective proofs queries random references region relational respect retrospective russian science sciences second selkow selman sentence separable sere short siam slozhn society springer steklov structure surface symbolic symposium system tarjan teor tested testing that thatcher theoretic theory there this thus time tree trees triconnected tutte valance valence variable variables verlag vetlag vlogv volume vychisl weisfeiler which width with wong working zachos
http://doi.acm.org/10.1145/335305.335398	74	Polynomial-Time Approximation Scheme for Data Broadcast	access acharya advanced affect algorithmica algorithms ammar analysis analyzing anily annual appear approach architecture aspects asymmetric atis autom badrinath before bestavros bhatia broadcast broadcasting brown bulletin chan changing channel channels chin classes cliffs comm communication communications comp computing conf consider constructions contr control costs cunha cycles cyclic data delay design discrete disk disks dissemination disseminationbased distributed distribution document does efficient empty energy engineering englewood environments evaluation expected factor files filtering from gecsei genesis given glass golden hadley hall hameed hassin hawaii hofri holte http idle ieee imielinski immediate indexed indexing individual infocom information initiated inserting instances integer inventory itai just kenyon khanna larger lemma lemmas liberatore lncs loth maintenance management math message messages minimizing mobicom mobile multiple naor networking nonuniform nsky obtained omitted once operation optimal optimality otherwise over packet paging performance periodic perspective pinwheel policy positive preemption prentice problem proc proceedings proe proof published publishing random ratio realtime references response rosberg rosier rutgers same scaling schabanel schedule schedulers scheduling schieber sections sept september server service several shekhar shilo sigmod single slots soda some stacs states stays stoc stretching symp syrup syst system systems tasslulas teletext that then theor theory thesis this time times trans transactions transmission traveller tulch under uniform university useful user vaidya varvel videotex vishwanath viswanathan weighted where while whitin wireless wireline with wong zhou
http://doi.acm.org/10.1145/335305.335308	2	Satisfiability of Equations in Free Groups is in PSPACE	akad algorithm algorithmic also alto amer american antiinvolution appear appendix applications assoc available california cambridge cgut chile cielski clef clei combinatorics communication complexity comput computer conditions constant constants construct contractible decidability departamento diekert dokl durnev each easily encodings english equation equations exponential extends finite first focs following foundations free generators group groups guti hold holds http icalp ieee ierrez informatics ingenieda inst interna izvestiya kmelevskii kogcielski latin lemma lempelziv list lncs logical lorents lothaire lyndon mach makanin matemgtica math mathematical moreover nauk observation only pacholski palo personal plandowski positive press primitive problem problems proc proceedings proposition pspace razborov recursive references relation report representation reprinted rrez russian rytter satisfiability satisfiable satisfied sbornik science semi semigroup semigroups sets solution solvability some soviet space sssr steklov stoc studying such symposium system systems technical texts that their theoretical theories there tional trans translation trudy universal universidad unknown ussr wesleyan which with word words yaroslavl
http://doi.acm.org/10.1145/335305.335389	69	Rapid sampling through quantum computing*	algoritbnas algorithm algorithms also amplitude annual applegate arbitrary available bernstein biham biron bounds boyer brassard buhrman ceedings chaos classical cleve communication communications complexity computation computer computing concave conference counting database deutsch distribution error fast focs fractals framework functions fundamentals generalized grassl grover haystack helps hoyer http initial integration international jozsa kannan lanl lecture letters lidar london mechanical mechanics nasa needle notes phys physcomp problems proc quant quantum rapid references royal sampling science search searching small society solitons solution springer stoc structured symposium tapp theory tight vazirani verlag wigderson wolf zalka zero
http://doi.acm.org/10.1145/335305.335408	82	Better Algorithms for Unfair Metrical Task Systems and Applications	aald achlioptas acms adversaries adversary against algor algorithm algorithmic algorithmica algorithms also amortized analysis annual appeared appendix application approaches approximating approximations arbitrary associates assume assumption bartal because between blum bound bounds bureh butch caching check chrobak claim coefficients combined combining communication competitive competitiveness computation computer computing configuration configurations constrained costs coustrained decreasing define defined derivative dimacs discrete distance distances done dual editors effectively efficiency enough equal european every exists expression factor fiat file first flip follows formula foundations from function functions games generality given hence however identical implies information ings into irani isomorphism journal karlin karloff karp large larmore left lemma limit line list lncs local loose loss lower luby manasse manuscript mathematics mcgeoch metric metrical metrics modification modified motion multiplied need needs next noga nual observation online only original pages paging partitioned planning points polylog potential prelimanary probabilistic probabilities probability problem problems proceed proceedings proof prove rabani randomized ravid rcompetitive reasonable references ries rudolph rules same science second seiden semireasonable sequence server show siam side similar simulated simulates since sleator snoopy space springer strongly such suffices syanmetric symposium systems tarjan task technique that their theoretical theory there therefore this thus tmweighted tomkins tree trmlslating umts unfair unweighted upper used using verlag version volume where whereas which with work young zero
http://doi.acm.org/10.1145/335305.335351	44	Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching	abstract access acta advanced algorithm algorithmica algorithms alphabets alphanumeric american amir analysis andersson annual apostolico appear application applications approximate array arrays association atlanta automata automaton baeza balanced beach bentley berlin between bielefeld binary biology blumer bottleneck brazil breaking brodal cactus cambridge carleton carnegie case chapter chen clark coded colloquium colussi combinatorial communication compact complete computational computer computing conference construction crochemore cross data database department dept dictionary discrete economical editors efficient ehrenfeucht engineering entire error errors experience extended external farach fast ferragina file files florida foundations fredman fsttcs galil geometry georgia germany giegerich glasgow glimpse gonnet grams graphs grid grossi guages guimar gusfield hall haussler heide hirschberg ieee iinen iliopoulos implementation index indexing indices inen informatica information institutes international inverted irkk irving jacobson journal july june keselman knuth koml kurtz landau large larsson lazy lecture lempel letters lewenstein line linear lncs logarithmic london look machinery manber manzini matching maurer mcconnell mccreight mellon memory method miami moffat monien morris morrison munro muthukrishnan myers myriad nato nilsson notes number optimal orthogonal overcoming overmars oxford paderborn pages parallel parentheses parsing patricia pattern perrin personal planar practical practice pratt prentice press proc proceedings processing programming quences queries ramamohanarao raman randomized range recife recognizing reducing references repetitions report representation requirement retrieval retrieve rodeh rytter sahinalp schieber science sciences search searches searching second secondary seiferas self sept series seventh sheared siam sieniec signature size small smallest snider software south space sparse springer srinivasa static storage storing stoye string strings structure structures sublinear subwords succinct suffix sutinen swanson switching symmetry symp symposium system systems szemerddi table tables technical technology text texts theoretical theory thesis through time tool transactions transducers tree trees ukkonen universit university usenix verlag versus virtues vishkin vitter volume waterloo weiner willard winter with words workshop worst yates york zaroliagis ziviani zobel
http://doi.acm.org/10.1145/335305.335392	70	Normal Subgroup Reconstruction and Quantum Computation Using Group Representations	abelian above abstract advances after aikerai algorithm algorithms alon also always amer andkwith annual appearing appendix argument aspects associate associated august azlo back beals been before being boneh both boundary boxes called case cell cells class classes clearly coincide collection column computation compute computed computer computing conjugacy connected consist consisting containing coppersmith coprime correspondence corresponding coset cosets cryptanalysis crypto cryptology customary cycle cycles cyclic daniel deal decomposition decompositions defined definition denote denoted denotes depends determinant diaconis diagonlize diagram dimension dimensional discrete disjoint distinct doing each eases easily easy editor efficient eight element elements equations ettinger even every example explicit exponent expressed extended factorization field figure finally find finite first fixing following formula four fourier from function functions furthermore general generated generating generators getting give given gives group groups hamiltonian have having hcyer hence hidden hook hooks identify including indicated integers intersections into invariant involves irreducible isomorphic isomorphism iwith joel john journal kernel know known last laxl lecture length like linear lipton logarithms lttaojii mapping march mark math matrices matrix means measure method might minus modkl modn murnaghan nakayama natural needs next nine ninth nlkx noga noncommutative normal notation note notes notice notion number obtained october oneto only ordered over pages particular partition partitions paso permutation persi peter placed play polynomial positive possibilities possible power prime primitive probabilistic procedure proceedings product quantum quaternin random reader realizing references remarkable removal removed representa representation representations results richard right ring robert rockmore root rows rule same sample sampled samples satisfy says science second separately sequence sets shor show shown siam sign similar simon skew smaller solution solve solving some sons spencer springer stand start step steps still structure studied subgroup subgroups such sufficient suppose symmetric symposium system systems tableau take taken texas that their them then theorem theoretical theory there therefore third this those though three time times tions together transform transforms trier twenty unity university unordered verlag vertical very vmue volume want well where which wiley will with written young zkxzt
http://doi.acm.org/10.1145/335305.335349	42	Higher Lower Bounds On Monotone Size	advances ajtai akad algorithm algorithms almost alon also amano amma andreev annals annual appear applied approximation approximations argument arguments babai bait behave berg bertc beulwi bits boolean boppana bosi bottleneck bottlenecks bound bounds circuit circuits combinatorica complexity computation computational computations computer computing conference construction corresponding corresponds counting criterion cutting defined degree depth distributed distribution distributions dokl dolk each easy editor eglnv elsevier english even every fast field finite formulae foundations fuast function functions furthermore fusasi general given goldreich haken handbook hastad hierarchy ieee independent independently individual induces itai journal jukna just leeuwen limits logic lower luby manuscript maruoka math maximal method micali monotone most nauk nisan note number obtaining optimal oracles over parallel parity pcnp pith planes point polynomial polynomials possible potential preparation press prime probability problem proc proe proofs pudlak pure random randomized randomness razborov references requiring research resolution russian saxe science seed separating show simon simple sipser sits size small some soviet space sssr struction structures such sunflowers symbolic symmetric symp syrup that theoretical theory there this time translation tsai ulfberg uniform uniformly uses values variables velickovic volume wigderson wise without
http://doi.acm.org/10.1145/335305.335324	17	Compression Using Efficient Multicasting	acad access acta addison adler agbaria aher algorithms amer analysis annual arch architectures arith arithmetic august avoiding azar bandwidth baudetschen beame behrend berlekamp between beweis bounds bridging bull byers cambridge canad ceedings certain chandra coding combinatorics communication communications comp company computation computational computer computing concurrent construction containing culler decomposition depth design deterministic dilworth document dongarra edited efficient eicken einer elements fich finding forum foundations functions furst gerbessiotis gibbons global goodrich graham guha heterogeneous hopcroft ieee improved information integers interface jacquemin john johnsson journal june karp krawitz lecture limited lipton local logp london long lower machines mansour massachusetts math matias median memory message model modeling models multi multicasting naor networks newman nieuw nisan note november numbers october offs only ordered pages parallel partially partitions party passing patterson physics power pram prams press proc proceedings processor progression progressions proof protocols publishing ragde ramachandran ramsey random randomized read reading realistic references relations resources restrictions rodl roth rothschild sahay santos schauser schieber science separating separation series sets short siam sinha siniolakis small sons sorting spencer standard stoc subramonian surveys symmetric symp symposium syrup szemer techniques theorem theory three threshold throughput time towards trade tradeoffs ullman university utilization valiant vermutung vishkin waerden wesley whitehead width wigderson wiley wisk with write yesha
http://doi.acm.org/10.1145/335305.335370	59	Approximating the minimum bisection size	algorithms analysis annual appear applications approach approximability approximate approximating approximation arora average benczdr bhatt bisection boppana case company complete comput computer computing conquer cuts dense designing divide edge editor eigenvalues feige finding flow foundations framework garey good graph hard haxd hochbaum ieee inform instances johnson jones journal karger karpinski krauthgamer layout leighton lett manuscript maxflow minimum multicommodity nphard optimal pages partitions polynomial preparation problem problems proceedings process publishing references saran schemes science shmoys siam simplified solving some stein stockmeyer symposium system their theorem theorems theoret theory time twice uniform vazirani vertex vlsi with within
http://doi.acm.org/10.1145/335305.335357	50	Are bitvectors optimal?	academic association babai bollob bounds brodnik chaudhuri checking chvgttal circuit codes complexity computations computer computing constant covered deterministic discrete disjunctive distribution dyachkov elias erdgs families fiat fiiredi finite flower fortnow graphs hashing hypergeometric implicit informatsii israel journal lecture length levin machinery mathematics membership minimum munro noar nonoblivious notes others pages peredachi polylogarithmic prankl press probe problems problemy proceedings radhakrishnan random references restrictions retrieval russian rykov schmidt science search sets siam siegel simple some space stoc szegedy tail time union which
http://doi.acm.org/10.1145/335305.335309	3	Setting 2 variables at a time yields a new lower bound for random 3-SAT	above academic accuracy achlioptas alamitos algorithms amer analogously analysis annual appl applications applied approximating approximation arithmetic artificial assoc austin automated beame bollob borgs boston boufkhad bound bounded bounding bounds brace broder bull case certain chao characteristic chayes combin combinatorics comm complexity complicated comput computation computational computer computing condition conditions conjecture continuous convex cook cornput cost dations davis deduction defined defining derived determining diaconis differential discrete ditterential dividing dubois each eatcs edition entropy equation equations examples fact facts fernandez fififi finding following follows formulae formulas foun foundations francisco franco friedgut frieze from function future general generating gets goerdt goldberg graph graphs greece guaranteed haken handbook harcourt hard heights heuristic heuristics ieee industrial inequalities initial inspection instance instances intelligence interval intractability janson jovanovich jump kamath karp kirkpatrick kirousis kranakis krizanc ksatisfiability kurtz kwlv left levesque limits linear lipschitz literal logemann loveland lower mach machine maftouhi majorization mandler manuscript many maple markov marshall matchings math mathematics matters maximum mean mechanics mick mitchell model monasson motwani nature necessary nedialkov note numerically occupancy odds olkin oper ordinary pages palem past paull phase philadelphia phys physics piecewise piscataway pitassi pittsburgh point points poisson population present press probab probabilistic probability problem problems procedure procedures proceedings processes program proof properties propositional prove providence proving publishers pure putnam quantification rain ralcom random redfern reed references release resolution respective results returned rigorous rounding santorini satisfiabil satisfiability satisfy scaling science search selman shake shaker sharp show siam side similaxly simple since sipser society solution solutions solving some sparse spirakis springer stamatiou statistical strict strictly structures submitted substituting such suen sufficient survey symposium system szemer tail that then theor theorem theoret theory therefore thesis third this though threshold thresholds toronto transition transitions tricritical trivial troyansky typical university unsatisfiability upfal upper used using value values vamvakari variables vega verify verlag were will wilson window with workshop wormald yields york zecchina
http://doi.acm.org/10.1145/335305.335318	12	Improved Algorithms for Submodular Function Minimization and Submodular Flow	above after again algebra algorithm algorithms amount andrfis annual appear appl application applications apply applying approach arcs austria belgium breach brood burkard calls capacity certain checked combin combinatorial combinatorica compute computing comu consequences corollary cost costs could cunningham deduced demands described discrete discussion done edge editors edmonds efficient ellipsoid embed explained fast faster feasibility feasible find finding finds fixed fleischer flow flows found frank fujishige function functions giles goldberg gordon graphs graz grotschel hanani have however implies integer intersection iwata japan jctb jols jordfm journal june just linear lncs lndust louvain lovasz math matroid matroids maximizing maximum mccormick membership method minimization minimizing minimum modified modify more neuve objective obtain obtaining oper optimal optimization order pages paper phases points polyhedra polynomial possible preprint price prices problem problems proceedings programming queyranne reduced references relation repeat report reveal reveals sauer scaling schrijver section shigeno sign since slightly snheim specified splitting springer start strongly structures submitted submodular subroutine suffices symmetric symposium systems tardos tarjan technical test testing that their then theorem theory this thus time uses using value variant vector vectors volume which with woeginger zero zhang zimrnermann
http://doi.acm.org/10.1145/335305.335333	25	The Risk Profile Problem for Stock Portfolio Optimization	accumulates after again alexander algorithm algorithms american annual applications approximating approximation assign assuming assumption bailey barrier based before below beyond binary bodies border broken case cents chains column combination combinations combinatorics combining computed computer computing condition conditions consider considered constraints construction contingency convex correspond corresponds created creation decomposition define different distribution distributions dividing dollar during dyer each easy edition entries entry equal error exactly expressed figure first fixed flow following follows foundations frieze from furthermore given goldberg hall helps idea ieee into invested investments iteration iterations joint journal just kannan last leaving level line linear linearly logk loss lost lovasz lowest manner markov mathematical matrix maximizing mount next number only pages pairing pairs polynomial portfolio precision prentice probabilistic probability proceedings program proof provably providence random randomness reduced references repeated repeating represents resulting return river saddle sampling satisfy science sets sharpe similar simonovits since society solve some stocks stop striping structures subject summed sums suppose symposium table tables tark that theorem these this thus time tree under units upper used variable variables volume walks where with within worst
http://doi.acm.org/10.1145/335305.335340	33	Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas*	above addition additivity after algebraic algorithms also annual applications applied approximate approximation area articles aspects assume balance balancing between bhatt bolyai both bounded bounds budapest california call cases circuits claim collection collections complete complezity computational computed computer computers computing connecting consider considerations crossing decomposition define defined denote designing discrete dissection dity efficient either even every fast flow following follows foundations framework francisco freeman full garey geometry graph graphs greater guha guide have hold holds html http ieee ifwt index inflate inflating interned intractability intuitive issues johnson kely kora larger layout layouts leighton leiserson lemma lipton local manuscript mathematics mathematieal methods most multicommodity naor nested node npcompleteness number numbers obtained paper parent partitioning planar press problems property proved rain rebalance recall references returned root schieber science sciences separator shahrokhi siam sibling siblings similarly since smaller society solving sssv step studies subtrees super symposium syracuse system tarjan than that their then theorem theorems theory tmax tmin tmrn transactions transformation tree trees triviality ullman univere upcoming using valiant vlsi weight weighted weights where which with york zero
http://doi.acm.org/10.1145/335305.335373	61	Clustering for Edge-Cost Minimization	above academic accomodated acknowledgments advantage advantages agglomerative algebraic algorithm algorithme algorithmic algorithms america american among analyse analysis annual appear appears application applications approximate approximation arabie arable arora ascendante aspects association attention attracted australian authoritative automata automation aware bartal based basford basu been benz berkeley bern biometrics boros botany both cahiers california cavalli cells centered centers chaine chajne chapman charikar ciproques clarify classification cluster clustering clusters combinatorial combinatorics comp comparison complete complexity computations computer computing concerning conf connected considerable consistency constant construction containing contains contemp control convergence convex cormack cornput corresponds cost criteria criterion cuts danndes dannges data dekker dense depend described diagrams different dimension dimensional dimensions discr discrete discussed discussion discussions domain drineas dual dubes dumka earlier earliest edelsbrunner editor editors edwards effective efficient either elimination empirical environment eppstein euclidean examination examples exhaustive existing extensions facility factor fall fernandez find finite first fisher form foundations framework freeman frieze full function functions garey generalized generally geom geometric geometry global glushkov gonzales gordon gower graph graphs gravity gray greene group grouping guha hall hammer hansen hard harm hartigan have help helpful hierarchical higher hilbert hochbaum homogeneity however hubert hyperlinked ieee image imai inaba increasing indyk inference inform instances interesting into intra islvar jain jaln jancey jardine jaumard johnson journal juan just kannan karger karp karpinski katoh kenyon kinds kiseleva klain kleinberg kleitman kluwer kmedian known large lead limitation lindenstrauss linial lipschitz list literature lloyd location london macqueen magen malik manuscript mappings marcel march math mathematical mathematics matrices maxcut maximum mclachlan means median medians method methods metric miller minimization minimize minimum mirkin mirldn mixture mladenovid model models monotone muchnik multidimensional multivariate must naukova neyman normalized novikov nphard numerical objective observations optima optimal optimize optimum other over pages pairs paper partial partition partitions pattern plenum point points pollack pollard polynomial preferable prentice press primal principles probabilistic probability problem problems proc proceedings programme proof proposed publishing purposive quantifier quantization quite rabinovich raghavan random randomization randomized rarchique reading reasons recherche recognition reduces reducibility reduction references regarded regions related relative remote representative restriction result review rota russia ryzin sabin sahni same samples sampling scaling scheme schemes science scientific scott section segmentation selection sets sforza shlezinger shmoys siam sibson simplified since sneath soete sokal solutions some sometimes sources space spaces specifically squares star statis statistical statistics step stockmeyer stratified structures studies subject subsequent such surveys switching symons symp symposium syrup tardos taxonomy techniques thanks that thatcher theor theory this time touching trans unsupervised useful variance vazirani vega vegas vempala version very vinay vision voisins volume voronoi ward weighted weights whey which wigderson wiley will with within without work world
http://doi.acm.org/10.1145/335305.335320	14	On the Approximability of the Traveling Salesman Problem	above achieved aksk alon amit applying approximation arora bipartite bound bounding candidate combinatorics computing condition consider construct coverings denominator distinct each edge edges enough exactly exist expansion factor focs formula from further generate generated gives graph graphs hand have having here high holds ieee implies intractability labeled large least leaving left less linial lund manuscript many matching matchings maximized method most motwani need note number numerator observe order original pairs perfect possibilities possible probability problems proc proof property random references resulting satisfies show side since sizes some stirling subset substituting such sudan suffices sufficiently suppose szegedy than that their theorem there this total true union used using values vectors verification vertex vertices view weight when where which will with
http://doi.acm.org/10.1145/335305.335399	75	Approximating permanents of complex matrices	accuracy achieve algebraic algorithm algorithmica algorithms america analysis analyzed andrei annual application apply applying approach approx approximate approximating approximation arbitrary association barvinok been bolyai broder carlo carus chebyshev colloquia combinatorial combinatorica combined complex complexity computer computing definition deterministic discriminants each eighteenth entries estimating estimator even exactly experiments exponential factor frieze godsil graph gutman hard herbert holland imate inequality into jerrum john journal karmarkar karp linial lipton luby marry matching mathematica mathematical mathematics matrix methods mildly mixed monographs monomials monte negative north partitioning permanent permanents polynomial prob probability proceedings published random rasmussen references relative repeated repeatedly ryser same samorodnitsky scaling science sequence shown siam simple simply sinclair societatis standard stoc strongly structures subsequences symposium then theoretical theory this time trials trick unbiased valiant variable variance vazirani viewed weak wigderson with within
http://doi.acm.org/10.1145/335305.335338	30	Smoothing and Cleaning up Slivers	above adjacent advancing algor algorithm algorithms already also alternatively analysis another appear appi applications applies arch argument assignment assoc automatic average avoids backtrack based berg berlin between biting bound boundary carnegie case cavendish center cheng chew ciarlet class cliffs color coloring colors comm complex complicated comput computational computed concurrently connect connecting conquer constant constants constrained construction containing contains cornput covering create current damage defines degree degrees delaunay dept described design deterioration deterministic difference different dimensional dimensions direct discussion distance divide domain done drawback each edelsbrunner edges efficient efficientparallelalgorithm either element eliminate elliptic engin englewood engrg entire estimates example experimenting express extend exudation facelloand field find finite forbidden former formulation freitag freitagand frey frieze from front gain generation geom geometry germany gooch guaranteed hall happens have holds holland however images implementation implies improvement include increasing inside insights inspired inter interesting internat introduce jersey jones kreveld laplacian large latter leads leave lemma length lnternat location mach maximum measuring meets mellon mesh meshed meshing meth method methods might miller millerand most motion moving need ngor nlog north number numer numerical numet olliv only open original other outside overmars packing paper parallel partition penn performance permit perturb perturbation perturbations perturbed pessimistic pittsburgh plassmann point points possibly practical prentice proach probably problems proc processor processors produces property proves proving quality question radius ratio receive references refinement region relevance removed repair report represent result results roundtable runs same schwarzkopf separator serious share sharing shewchuck short shows significance simplices simplify since single sketched sliver slivers small smoothing spaced sphere springer step still strangand subtle such sufficiently swapping sympos syrnpos takes talmor tang teng tetrahedra tetrahedral tetrahedron that then theory there these this three time tori torus transition triangles triangulation triangulations tzng univ upper used using variation verlag version vertex vertices volume walkington weight well which while whole with worst worthwhile would
http://doi.acm.org/10.1145/335305.335356	49	More Theory Revision with Queries	advances american amsterdam angluin argamon artificial association attribute attributes based blum bound bshouty chapter clauses colt complexity comput conferences conjunctions counterexamples davis earlier editor editors efficient engelson exploring finitely first frazier from greiner hamscher hellerstein horn infinitely inform intelligence irrelevant journal kaufmann koppel learning littlestone machine many mateo mistake model models morgan national order pages patching pitt presence press queries query raedt reasoning references refinement regular research revision sets shrobe survey syst talks theory tractability troubleshooting version wrobel
http://doi.acm.org/10.1145/335305.335353	46	Approximate nearest neighbors and sequence comparison with block operations	accelerating addisonwesley agarwal algorithms analysis approximate arrays bernetics binary block capable cascades chang codes coin cole colton communication comparison complexity computation computer computing conf conference control cormode correcting correction curse databases deletions designing deterministic devereux dimensional dimensionality dimensions discrete distances document dynamic edit edits efficient embeddings euclidean evolutionary exchange expected farach fast fornearest foundations geiassemble gelassemble gribskov hausdorff high identification ieee indyk insertions journal karp kleinberg kruskal kushilevitz labeling landau lawler levenshtein lopresti macro macromolecules mass matching metrics micro miller models motwani moves nearest neighbor neighbors noise ostrovsky paradigm parallel paterson pattern patterns practice presence press primer problem proc proceedings rabani rapid reading recognition references remving repeated reversals rosenberg sahinalp sankoff sawhney scaling science search sellers sequence serial series shim similarity spaces stockton string strings sublinear symp symposium systems techniques theoretical theory tichy time tomkins tossing towards trans translation trees ukkonen using vishkin vldb warps with
http://doi.acm.org/10.1145/335305.335368	58	Finding Long Paths and Cycles in Sparse Hamiltonian Graphs	algorithmica algorithms alon annals annual approximability approximating aspects bazgan bondy canadian chvatm coding color combinatorial computer computing connected cubic cycle cycles degree discrete efficiently find finding from graph graphs guided hamiltonian jackson journal jrer karger large lawler long longest mathematics minim monien motwani nother optimal optimization other paths problem proceedings raghavachari references salesman santha science series simonovits simple small spanning subgraphs symposium theoretical theory third tour traveling tree tuza twenthysixth within yuster zwick
http://doi.acm.org/10.1145/335305.335380	64	Matrix-vector Product for Confluent Cauchy-like Matrices with Application to Confluent Rational Interpolation*	above algebra algebraic algorithm algorithms almost annual appear appl applications approach assertions assp assume available ball basel biirgisser bini birkh birkhauser boston boundary canchy case chebyshev circuit classical classified clausen codes complexity comput computation computations compute computer computes computing concatenation conf correcly correctly decoding degree delsarte depm diagonal discrete displacement distance doubling efficient eigenvector electrical element elements else engineering equals equations fast final following formulas foundations friedlander from functions generalized genin gerasoulis gohberg grundlehren have heidelberg heinig hessenberg hilbert http ieeb ieee iitl included input integer integers integral internat interpolation inversion kailath kallath kamp lemma less like linear lines ljung logd math mathematik mathematischen matrices matrix matvro ment methods moff morf multiplication multivariable nehari nevanlinna nevanlinnmpick next numerische olshevsky omitted operations operator operators output outputs paper partially perform physics pick pivoting polynomial polynomials positive potential precomputed presentation press problem problems proc proceedings proof rapid rational ready reconstructible recursively references related return review rodman rokhlin role rood rost sayed science sequences series shokrollahi siam society solution space springer stanford state step structure structured supeffast symposium system systems szego takagi tangential terms than that their theory thesis this time tional toeplitz transmission unitary univariate university user value vandermonde vectors verlag version vexlag volume where will wissenschaften with
http://doi.acm.org/10.1145/335305.335382	65	Query Strategies for Priced Information	abstract academic access adversary algorithm algorithms alpha always analysis appear array automata before believe best beta blum bollobas bolts boolean borodin bounded bounds cambridge case chalasani charging clearly clickshare commerce communications competitive complexity computation compute computer computing conf considering coppersmith corp cost could course data decision delivered details deterministic digital does dynamic each economic efficient electronic element elements engineering entail etzioni evaluating every extended extremal fails february ferguson find first fixed focs focuses following force foundationsfor framework from functions future game garcia gathering given graph hanks heiman home however html http icee ieee illustration information interact interuet interval intl jiang journal karp ketchpel knowledge koml koutsoupias kreps languages larger latency lead least libhome libraries line linear lower madani magazine matching micro minimum molina more motwani netbill network nikolaou nuts omit once opposed optimal optimality optimized overall page panel papadimitriou papers particular peak personal possible present press priced pricing princeton probabilistic problem proc proceedings programming prove pulleyblank raghavan randomized ratio read reducing references safeguarding sairamesh saks science search searching seen service setting shivakumar should siam snir soda some sorted straightforward strict subinterval subintervals sudan suggests suppose symposium system systems szemer that then theoretical theory this time total tree trees tygar umich university value vector waarts what when which wigderson will work would yaniv yannakakis yemini zhang
http://doi.acm.org/10.1145/335305.335321	15	Approximating the Domatic Number	acknowledgments advanced algorithm algorithmic algorithms ality alon always annual appear appl applications applied approach approximability approximating approximation approximations arnborg assignment author balanced beck berge bias bonucelli boolean bound cardi career celia chair chang chordal chromatic circular classification cockayne codes coloring combinatorial comp compendium complete completeness complexity comput computation computers computing configurations constant constraint constructions correcting cover covering covers crescenzi current decomposable degree dekker derandomization derived determine development difficult disc discrete discussions domatic dominating domination duality easy edges efficient error essentially exact factor families farber feige finally finding first follows found fractional freeman from fujita fundamentals garey girth give given goldreich graph graphs greedy guide hardness have haynes hedetniemi helpful holland http hunt identical ieee incumbent independent integral interval japan johnson joint joseph journal june kameda kann kaplan khanna kilian knowledge korea kratochvfl lagergren languages large least left lemma like line linear local location lovasz lovlsz lower lund lvll macwilliams main making marathe marcel mario math matrices maximization method micali minimization moran nada naor near networks nondeterministic nordic north nothing number obtained omitted open optimal optimization other pages partition partitioning peng perfect performance petrartk polynomial probabilistie probability problem problemlist problems proc process programming proof proofs proskurowski question questions random rangan ratio ravi references regular research reskin resource results satisfaction satoshi schulman seems seese sets shamir shown siam sided simple slater sloane slovaea small smallest some spaces spencer splitters srinivasan strongly structures study such sudan sufficiently symp symposium syst szegedy techniques telle than thank that their theorem theoretical theory these threshold time topics towards tractability tree upper validity version vertices waac wigderson wiley williamson with work workshop would yamashita yannakakis yield zelinka zero
http://doi.acm.org/10.1145/335305.335326	19	A Random Graph Model for Massive Graphs	abello acad acta aiello albert algorithm algorithms alon approach asymptotic august barab barabasi bases baxabasi bruce buchsbaum call cambridge characteristics chung comb combin combinatorics communication communities compiled component components comput computing conference connected connectedness connectivity critical cyber data degree diameter each edinburgh elsevier emergence emerging erdss european evolution external extracting faloutsos free from functional giant given graph graphs hung hungar indegree inst international internet jeong july kleinberg knowledge kumar labeled labs lamb large lecture luczak manuscript massive math measurements memory method methods michael models molloy nature networks note number october outdegree part personal phone point possible power powerlaw poznatl preece preprint probab probabilistic proc proceedings publ raghavan rajagopalan random raphavan records reed references regular relationships scale scaling science scotland september sequence series size sons sparse spencer strength structures surveys symposium theory this tomasz tomkins tomklns topology trawling typical using vertices vldb westbrook wide wiley with world wormald york
http://doi.acm.org/10.1145/335305.335385	66	A Guessing Game and Randomized Online Algorithms	able about acknowledgment advance adversary after afterwards agent albers algorithm algorithmiea algorithms also amortized amount annual another appear appendix applications approaches approximation arrival arrive arrived arrives assigned assume attempt average bahncard bahneard bartal based been before behavior being best better between black blum borodin bought bound bounds busy butch buying buys caching calculate calculated calculation card carnegie case characterized chekuri chen chooses clearly closed coefficients combinatorial combinatorics communications competitive completed completion complexity computation computational computations computer computing concern conference consider consisting constant continuous continuously contributes copy corresponds cost costs could create customer david days decide define delay deliver delivered delivery department description desired details deterministic directly discount discrete distance does dollar dollars dooly duration dynamic each earliest easily economic edge edition effectively efficiency eindhoven either encode entitles equivalent every evil evle exactly exists explain ezvj fact factor fashion fiat figure final find finely first fixed fleischer followed following follows forever form formally forward foundations freedom from further game games general generality give given gives goal going goldman good grows harder have high holds hoogeveen however identical ieee immediately implies imreh included independent infinite information initial initially inputs instance instead integer international interruption jobs journal kalal karlin karp know koga larger last least length letters line linial list listed load longer loss lower machine machines makes makespan manasse manuscript mathematica maximum mcgeoch means measure mellon mendel metrical migration minimize minimizes minimizing model more morgenstern motivate motwani multiple must natarajan netherlands network neumann node nodes noga nonuniform note number obtain once online only operations optimal optimization original other over overall owicki page pages paging paper parallel passed pays performed pick picks plus polylog positive possible power practice presented press previous price princeton probabilistic problem problems proceedings processing programming proof proofs prove proven provide proving purchase purchased purchases purely question randomization randomized ratio reached reader readers real refer references referred release remaining rent rental renting replicated replicates replicating replication report request requested requests requirement research result results round rounds rudolph rules rumple running saks same schedule scheduler schedules scheduling science scott second section seem seiden send separately serve setting short should shown shows siam simple simultaneously since single situation size skiing skis sleator snoopy solution some specified spends start started starts stated stein stop stopping stops stougie straight summary symposium systems table tardos tarjan task technical techniques technology tedious than that their them theme then theorem theorems theoretical theory there therefore these thesis this time times tomkins total toward type types undetermined unfair unfamiliar unified uninterrupted university unknown unpublished until update using valid values variations version vestjens vvln waits were what when where whether which while wigderson will wish with without worse would yaniv yields
http://doi.acm.org/10.1145/335305.335396	72	On quantum and probabilistic communication: Las Vegas and one-way protocols	access adami address advice aharonov algorithm algorithms almostquadratic ambainis applications aspects automata beame bennett bits boolean bound bounds boyer brassard buhrman caltech cambridge cerf channels chasing circuit circuits classical cleve codes coding communication comp complexity comput computation computational computations computed computer computing conference considered database dense determinism deterministic different discr discrete dokl durig duris efficiently einsteinpodolsky entanglement entropy error estimates even exponential factorization fast finite formula formulae found freivalds function functions galil generalizations grover gruszka halstenberg hebrew holevo hoyer hromkovi ieee information inner interscience intersection iporuk journ journal jumping kalyanasundaram kitaev klauck known kondacs kremer kushilevitz lawry lecture lett limited logarithms lower master math measurement mechanical mixed modes more most much nayak news nielsen nisan nondeterminism nondeterministic notes number operators parallel particle people phys physcomp physical physics physis pointer polynomial polynomials ponzio power preskill press prime probabilistic probability problems proc product proe quant quantum radhakrishnan random randomized reducing references reischuk results review revisited rolim rosen round rounds roychowdhury sampling schnitger science search searching separation shma shor siam sigact size some springer state states strengths substituting symp symposium syrup tapp than theoretical theory there these thesis tight time tion transmission transmitted univ university vatan vazirani vegas venkatesh versus watrous weaknesses well which wiesner wigderson wiley with wolf workshop zalka
http://doi.acm.org/10.1145/335305.335402	78	Self-Testing of Universal and Fault-Tolerant Sets of Quantum Gates	accuracy acts adleman again aharonov algorithms almost also analyze anti apparatus appendix applications apply assumption basis berkeley both bounds calculation california case characterization characterizations checking cirac circuit circuits combination combined comes complete complexity comput computability computation computations computer computing conclude conclusion constant coordinate coordinates correcting correction cpso cryptography decoherence decomposition defined defines demarrais denote density directions discrete discussion distance entangled equality equation equations equi error every fact factoring fault first fixed focs fogs follows form four from functional gate generalized generate hand have hence heory holds huang hypothesis identity imperfect implies imply induction inequalities inequality kitaev knill lafiamme laflamme lanl last leads lecture left lemma linear linearity lipton lloyd logarithm logic london math mathematical mathematics matrices matrix mayers memory mixed models moreover most negative nisan nonpositive notes obey obtain onto orthogonal orthonormal other pair people phys plane point points polynomials positivity power poyatos preskill preskiu proc process products program programs projecting projection proof prove proved pure quant quantum qubit ralentwith reducing references relation representing resilient restriction restrictions result right robust robustness rubinfeld russian same satisfy satisfying scheme science second self series shor shot show shows siam side similarly simon simplify since some ssatisfies state statement states stoc straightforward such sudan sufficient superoperator suppose surveys symmetric symmetrical tensor terms testing that then theorem theoretical theory there therefore these thesis they this three threshold thresholds thus tolerant true uniquely universal university using vectors verify where which whose will with written yields zoller zurek
http://doi.acm.org/10.1145/335305.335341	34	On the Decidability of Accessibility Problems	academic acbfl access acfl addison addisonwesley adds aeyclic affect again alamitos algorithm also alternatively analysis another anything applicable application applying appropriately april argument assume attenuating august authors automata base based because bedford bell belong berlin between blaze both budd bylemma cacti cannot capability case cases checking cheiner claim classes clearly closed closure cmbcfl combinatorics communications compliance computation computer computers conclude conference consider contained contains contradiction corporation correspond corresponding corresponds could created creates cryptography cycle dafl dave decentralized deciding define definition defl degree delete deleted deletes deletion denote derivation derivations design directe directed discussions distributed does each easily edges editors either employing empty establish eventually exist exists explained exposition fact feigenbaum finally financial finite first following follows form formal foundations from furthermore gives giving grammar grammatical harrison have helpful hence here hold holds hopcroft however hypothesis iedet ieee implies induction infinite information insert inserted inserting insertion inserts interf interface interfaces international internet interpretation into introduction ioannidis issues jensen john journal july keromytis know kormannfor laboratory lacy languages lapadula latter least leftist leftmost lemma length less like linear lipton lncs lothaire management many march mark matrix means mexico michael mitchell mitre mobile model models modified modify monotonic multics must necessary node nonempty note nothing objects observe obtain obtained oleg omitting only operating operation operations order otherwise pages participate participates path policymaker possible preceding prefix present preserve preserves press privacy proc proceeds production programming proof proofs property protection prove rebecca references reflexive reflexivity relation replacing replicate report research respectively result reverse right riter role rubin rule rules ruzzo safety saltzer sandhu saraswat schematic schemes schroeder sciences secure security seen select september sequence setting shannon shorter show showing similarly since snyder society some somehow springer start step still strauss string strings subject subsequences such suffices suffix suppose symbol symbols symposium system systems technical than thank that then theory there therefore these this three time transactions transformation transitivity true trust turn typed ullman under unexplained unified using vacuous valid verifies verify vertex vitek volume wesley when where which while will with words would wright yielding yields
http://doi.acm.org/10.1145/335305.335339	32	Approximation algorithms for geometric shortest path problems*	agarwal aleksandrov algorithm algorithms approximating approximation bajaj bound canny chen claxkson compter comput computer computing convex decompositions focs foundations geometric july lanthier lncs lower maheshwari motion october path paths planning polyhedra polyhedron problems proc references reif report robot robustness sack school science shortest siam soacm stockholm swat symp symposium technical techniques theory varadarajan weighted
http://doi.acm.org/10.1145/335305.335354	47	Near Optimal Multiple Alignment Within a Band In Polynomial Time	acad acids actually addison algorithms algorithrnica algorithrns aligning alignment altschul appear appl approach approximate approximation atlanta average averageconsensnsalign averageconsensusalign bafna band better biol biological biology both bounds bull cabios cambridge case chao chapman classes combinatorial communication comparison complexity computational computing concluding conf consensus constraints control cornp cornput cornputational cost course described diagonal diagonalalign disc duxbm easier easily edits efficient ence enzyrnol error explain extended fast fasta fastp fickett find finding follows formed former formula frequency from function general genomics given graph guaranteed gusfield hall have hope hopeful improved inequality instead interesting introduction issue jiang just keceeioglu know kruskal lancia later lawler lemma lenhof letters libraries linear lipman look majority manuscript many matching math matrix median mehlhom methods miller minimum model more motwani multiple mutzel myers natl notice nucleic optimal optimization orrn papadimitriou pattern pearson pevzner phenomenon phylogeny polyhedral polynomial positions practice press probability problems proc progressive protein proved ptas quadratic raghavan randomized rapid ratio ratios ravi references regions reinert remarks respectively rnacrornolecules roughly routing sankoff scheme schemes score searching selectivity selznick sensitivecomparison sensitivity sequence sequences siam similar smith spanning special specifically specified spouge stars statistics step stone string strings surpasing syrnp syrup system tang than that then theory therefore this those thus time tools tree trees ukkonen univ university vingron wang warps waterman wesley where with within work yarmakakls zhang
http://doi.acm.org/10.1145/335305.335401	77	Improvements in Throughput Maximization for Real-Time Scheduling	adaptive algorithm algorithms aligning allocation amotz annals annual applications approach approx approximability approximating available berlin berman bouck case communication competitiveness computational computer computing conf conference control controlled dates discrete dynamic earnshaw edited foundations fragmented freund full geometry graphics grid guha hafez heidelberg http ibaraki independent interval jacm january jobs jose journal kise koren large late lawler lecture line lipton machine machines manuscript miller mine minimize mishra mobile multimedia multiple naor nato networking networks notes number online operations optimal over overloaded overmars overview packet preemptive preliminary problem problems proc proceedings prof programming publication raghunathan rajugopal rate ratecontroued ready real references research resource robust rosier sahni scheduling schieber science sequences series shasha siam single site solvable source spie spieksma springer stoc submitted symp systems tasks theoretical this throughput time tomkins transmission unified verlag version video wang wireless with yehuda zarki zhang
http://doi.acm.org/10.1145/335305.335364	56	Connectivity and Inference Problems for Temporal Networks	acknowledgments addition algebraic algorithms allgemeinen another appl applications approximating approximation april arborescences arch arcs bailey baker berman broadcast broadcasting bulletin bumby call canadian combinatorial communication complexity computational computer computing connected consider consisting contain could courbes cure database demers detection directed discrete discussions disease diseases disjoint each easy edge epidemic every failure finding focs fortune from function fundam gauches generalization gossip gossiping gossips graph greene guruswami hafner hajnal hardness hauser have hayden hedetniemi homeomorphism hopcroft however ieee ifip incoming indices infectious investigation irish karp khanna kuratowski kurventheorie labeled larson least levi liestman maintenance math mathematical mathematics mccormick menger methods miller minimum minors minsky model most motivated near network networks nieuw nodes objective open operating optimal other path paths personal press principles probl problem problems proc proof protocols question rajaraman ramification rapid ravi references related renesse replicated respecting results robbert robertson root rooted rumor scheduled science service seymour shenker shepherd shostak simchi size slam stuygis style subgraph subset surv swinehart symp symposium systems szemer telephone telephones temporal terry thank that them then theorem theoretical theory there this tightest tijdeman time timerespecting topologie valuable verify vertex vertices vulnerability were wfiat which will wisk with wyllie xiii yannakakis yaron
http://doi.acm.org/10.1145/335305.335312	6	Randomized Metarounding	algorithmic algorithmica algorithms approximating approximation asymmetric bounds cart cheriyan chernoff combinatorica conference congestion connected deterministic edge global good guided hagerup improving information ipco isaa letters multicast multiterminal problem proceedings procensing proofs provably raghavan randomized references rounding routing salesman scheme sebo smallest soda spanning subgraph szigeti technique thompson tour towards traveling vempala voecking
http://doi.acm.org/10.1145/335305.335315	9	On the Efficiency of Local Decoding Procedures for Error-Correcting Codes	ambainis annual approximation arora aspects babai beaver bounds characterization checking chor communication complexity computational computations computer computing expt february feigenbaum focs fortnow france goldreich hardness hiding icalp information instances journal kushilevitz lecture levin lund motwani multi nisan notes oracle pages polylogarithmic preliminary private probabilistic problems proc proceedings proof proofs publishable queries references retrieval rouen safra science simulations springer subexponential sudan symposium szegedy theoretical theory time unless upper verification version volume wigderson
http://doi.acm.org/10.1145/335305.335377	63	C-Optimization Schemes and L-Bit Precision: Alternative Perspectives in Combinatorial Optimization*	academic advances algorithms among analysis angeles annotated annual anomalies applied approximate approximation arithmetic bibliography binary bounds california chicago combinatorial complexity computational computations computer dimensional dual editor editors efficient exact fixed floating foundations graham greenberg hard heuristic hochbanm hochbaum horowitz ieee illinois integer jackson journal karmarkar karp kluwer laboratory lateness lenstra line logic management manuscript mathematics maximum miller minimize minimum mixed multiprocessing nonidentical notices number operations optimization orlin packing pages paper plenum point postsolution practical preprocessing press problem problems processors production programming project publishers reducibility rejection report research results sahni scheduling scheme schemes school science search sengupta shmoys sigplan slam sloan standard stochastic symposium tardiness thatcher theoretical timing university using variables with woodruff working
http://doi.acm.org/10.1145/335305.335347	40	Space Complexity in Propositional Calculus	accordingly acknowledgment acta aeta again algorithms american appearing april arithmetic arithmetics assignments assume axioms beame boner bounded bounds branching buss calculus cambridge colloquium complete complexity computational computer computing conduct consequence constraints contradiction cook corollaries corollary deduce dicrete dimacs easy editors efficiency efficient electronic empty enough esteban every exponential feasible focs following formula formulas frege from full future galesi gives grateful have hence ieee implies independence induction inference inferred informatica ings interpolation journal jukna kozen kraj krajf kraji krishnamurthy list logic logical lower made make manuscript math mathematics modify modifying narrow natural naturally necessarily omit omitted once only pages particular past pigeonhole pitassi plexity polynomial possible present press previous principle proceed proceedings produce programs proof proofs propositional proved razborov read reckhow rectangular references refutation relative remarks replacing report resolution results rule rules sasson science search semantic sequence series several short showed similar simple since small space stalmark stoc strong study symbolic symposium system systems tautological tautology technical that theorem theorems theoretical theory this through thus together toran transition transversal tricky university useful variable variables volume where which wigderson with workshop
http://doi.acm.org/10.1145/335305.335366	57	Strictly Non-blocking WDM Cross-connects for Heterogeneous Netwdrks	academic addison algorithm also analysis another applications applied arbitrary architectures area assumption asymptotically available azizoglu bala bassalygo been bell blocking bound bounds cantor case channel communications complexity computer connect connects consider considered construct construction conversion converter converters could cross currently demand demands design differs disturbing doerr each efficient exchange fabrics fibers fixed from future general generalized given graphs guidedwave here hinton ideas identical ieee infocom inform informalsii initial input instance interchangers interehangers interesting intersect introduction journal kleinberg klogk know kumar less lightwave limited link links lower magazine mathematical mathematics memory mikkelsen modeling more multicasting multiwavelength must necting needed network networks nlkl nonblocking notion number october only optical optimal output over pages path pathwise peredachi photonic pinsker pippenger placement plenum possibilities presented press previous previously problem problems problemy proc proceedings protocols ramaswami rasala reading rearrangeable rearrangement reconnections reduced references remains requirements ring routed routes routing same sasaki satisfied schwartz section sense shannon shifting shown sium size soda somani some space spanke split stern strictly such suhramaniam switching sympo symposium system systems tech technology telecommunication telephone teletraffic than that their theory there thiagarajan this those topologies topology traffic translation transmission under underlying upper used using valiant valid variations volume wavelength wavelengths were wesley where whereas wide wilfong winkler with without wmdz work working works would york zirngibl
http://doi.acm.org/10.1145/335305.335400	76	Combining Fairness with Throughput: Online Routing with Multiple Objectives	addition additional admission afek after against algorithm algorithms allocation along analysis andrews annual another appendix applications approach approximate approximated arrivals aspnes assign assigned assigns assume awerbuch azar balancing bandwidth bandwidths bartal based been begins bertsekas better bottleneck bound bounded bounds byers cannot case cases circuit colton combining compared competitive competitivity complexity computer computing conference consider consisting construct contains continues control convergence converging data deferred define demers dependent depends desired determin determined deterministic discrete divided each edge edges effective either every exceed exists experience fair fairness farach fast fiat first flow flows following follows foundations from frugal gallager general generality generalized gets give gives global globally graph guarantee half hall have ieee implies included includes inequality infocom information integrated internetworking intersect intersecting intersects istic june kamath keshav kleinberg labelled least line lines link load local logarithmic logn logu long loss loth love lower machine made mansour math maximum megiddo model more most must need neither networking networks node nodes none number obtains online only optimal optimistic optimization order ostfeld otherwise pages palmon parekh permits phantom places plotkin plus poisson possible prefix prentice proceedings processor profit programming proof prove queueing rabani rain rate ratio receives receiving references request requests research route routed routes routing routings scheduling scheme science sequence services sharing shavitt shenker short siam sigcomm simple simulation since single sink sinks solution solving source sources suppose symposium tardos than that them then theorem theory there therefore these this those through throughput time topology total transactions unit using virtual waarts weight were where which will with without yields zhang
http://doi.acm.org/10.1145/335305.335362	54	Random Walks with "Back Buttons"	academic agent algorithms analysis assists barrett bedin browsing cambridge chains charikar coach combinatorial communications computing conference course denumerable factors first geometric grotschel higher horn human john johnson karlin kellem kemeny knapp kumar learns lieberman ljcai lovasz maglio markov mathematics matrices matrix minc motwani nonnegative nostrand optimizations personalize press princeton proceedings processes raghavan rajagopalan randomized references schrijver segments selker series snell sons springer stochastic symposium systems targeting taylor teaching that theory tomkins university verlag wileyand york
http://doi.acm.org/10.1145/335305.335403	79	Computing with Highly Mixed States	above acad algebras algorithm also always appearing archive associated automatically barrington being beneath between bijective both bounded bounds boxes branching call case cell cells chuang clear collection column complementary completely comput computation computer computing considering consistent consisting constant containing context corner correspondence corresponding cory course customary decomposes define deleting deletion denoted described determined diagram diagrams dimension dimensions dimp distributions does each engines ensemble even exactly example experimental explicit exponential exponents expressed fact fahmy february figure find finite first fixed fixes following formula from fulton gershenfeld given group groups hard harris have havel heat hoffman homomorphism hook hooks however http humphreys identify implies including infinite information inside integers into invariant involves irreducible isomorphic isomorphism itself knill laflamme languages lanl leaves legal lemma length lengths lett leung linear lloyd longer lower magnetic mapping matematicheskff means mishchenko mixed molecular must natl nature nielsen nonzero notation note notion nuclear number obtained often oneto order other over oxford paper particular partition partitions phys placed point polynomial positive possible power press probability proc process product programs projective proper quant quantum ranges realization recognize references repeating representation representations represep resonance restrict restricted restrictions right rows said same sbornik scalable scale schulman schur science sciences sequence shape shapes shown shows similarly simply simultanously since size some space spectroscopy springer stand state stated subgroup subspace subspaces such svmp symmetric system tableau tained taken tation that them then theory there these this those transformations true under unitary university usually vandersypen varieties vazirani vector verlag when where which whose width will with write written young zero zhou
http://doi.acm.org/10.1145/335305.335374	62	Exact Computation of the Inertia of Symmetric Integer Matrices	about absolute academic accuracy accurate actually algebra algebraic algorithm always analysis anderson annual appear appendix applics applied argument arithmetic bareiss basis behavior birkhoff bischof block blocks bound calls cart case chosen chris claredon clarkson clean close college column columns combining comp composed computation computational computations compute computer computes computing conditioning conservative could coupling croz ctbc culver curves decomposition definition demmel determinant diagonal domain dongarra each edition effective efficient ehmn eigenvalue eigenvalues ellmii england error estimate estimates evaluation exact example exposition express extendedprecision factor factors fairly faster figure finish floating follows form fortune found fourth from fthef geom geometry gives golub good graphics greenbaum guide hall hammarling have hence herstein high hopkins hypothesis ieee iiamii iiii iimi ilmll implies increases index indicates inst integer integral interesting into johns keyser krishnan lapack last lemma lemmas length less library limil linear little loan macmillan magnitude manipulation manocha manuscript mapc maple mathematics maths matrices matrix mckenney mean might mignotte modern more most nliamij nnamn norm normalized number numerical observed obtain occur open orthonormal ostrouchov over oxford paper parlett partition parts perturbation point points polynomial prentice presentation press problem problems proc proof publishing reasonable reduced references relative relatively rest results safe sample science second separately separates series shea siam sign similarly simple simplify simply since singular sjlvcfl sjlvl slightly solutions some sorenson spread springer static stewart straightforward subsets substantially summarizes summation survey svds symmetric symp tedious tend than that then theory these third this three thus tight topics trans uctured unimodular university used user using value verify verlag very viim where which wilkinson will with worst would write writing xerox xffllsl yield yields york
http://doi.acm.org/10.1145/335305.335314	8	Circuit Minimization Problem	acknowledgements akademii algorithmic algorithms american andreev annals annual another approach approaches approximation asano aspects association author babai bell berechnungskomplexit bound bounds brute buhrman cambridge certain characterization charles circuit circuits circult classes clementi cocoon collapse colloquium combinatorial combinatorics comments company complete completeness complexity computation computational computer computers computing conference consequences control conversion cook covering cybernetics decisive derandomization derandomizing described difficulties discussion doklady early editors eighth einige electronic eliminating english error exponential factoring factorization fiber fifteenth fifth first fizmatgiz force fortieth fortnow foundations freeman fruitful garey general generator goldreich guide half hardness having help here heuer hierarchy history hitting hochbaum icalp ieee imai impagliazzo impossibility improved information insightful integers international into intractability izika izvestiya jahresberichte jansen johnson journal kannan kibernetiki ksbler lautemarm lecture lemma lenstra letters lipton lower lupanov machinery manuscript many masek mathematical mathematics meinel method miltersen minimal more moscow nakano natural nauk near ninth nisan nonreducibility notes nual optimal optimization pages paper perebor philosophical pollard polynomial pomerance preliminary primality probabifistic problems problemy procedures proceedings processing proof proofs proving pseudorandomness publishable rackoff radio random randomization randomness razborov references relativized remarks requires research resultate results richard rigorous rofim rolim rudich russian science sciences search sets shaltiel shannon siam sided simulations sinclair sipser sixteenth size small society solving some sources soviet sparse springer stage stephen strassen subexponential super survey switching symposium synthesis synthesizing system systems technical terminal testing thank that theorem theorems theoretic theoretical theory third thirty this time tison tokuyama trakhtenbrot translation trevisan twenty twosided unless using verlag version versus vinodchadran volume watanabe weak wigderson wilson wishes yablonski york zachos zuckerman
http://doi.acm.org/10.1145/335305.335404	80	Quantum Bit Escrow	adrian advances aharonov allen also annual august barbara blum chau circuits coin computing crypto cryptology editor electrical engineering fidelity flipping gersho hardy ideal impossible jozsa kent kitaev lett lucien manuel mayers ment mixed nisan optics pages phys physica press problems proceedings protocol quant quantph references report santa secure sensitive solving states stoc symposium technical telephone theory tossing unconditionally with york
http://doi.acm.org/10.1145/335305.335337	29	Finding Smooth Integers in Short Intervals Using CRT Decoding	algebraic appear appendix applications arithmetic bers beyond bleichenbacher boneh bound chinese codes complexity computing coppersmith correction cryptanalysis crypto cryptology data decoding digital durfee equations error eurocrypt exiex exponent fact factoring follows from functions graham have hence howgrave ieee interpolation jenkins jullien knxnxl large lipton mixed modern nguyen noisy number observe polynomial press private proc processing proof prove real reconstructing reed references remaindering remark residue rubinfeld section siam signal simple since small soderstrand solomon solutions sudan system taylor that then used vulnerabilities whenever with
http://doi.acm.org/10.1145/335305.335346	39	A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs	able academic acta akademia algo algorithm algorithms algorithrns allender also amsterdam annals annual another applications approach arbitrary aspects australian based been before bipartite bonn bonnington bounded bounds budach canada case chapter chordal chrobak classes claw cocoon combinatorial combinatorica combinatorics comparability complete complexity components computation compute computer computers computing conclusions conference conservation constraint constructing contraction convex counting crystal cycles dahlhans dahlhaus data degree dekel dense design designing determinants devise devised difficulties dimacs discrete distributed does each easily easy editor editors efficient efficiently either electronic elsevier embedding embeddings encounter enforce enough enumerating even exist extend extension fact factors fast fifth find first fixed flow foundations fractional free from fstsjtcs fundamentals further galluccio genus goldberg graham graph graphs greater grigoriev groups grstschel guided hajnal hamiltonian handbook harary have holton hope however ieee independent inequalities informatica information inside integer international interval inversion isolating iteration iterations journal karl karpinski kasteleyn kastelyn kaufman known kozen least lecture lemma linear little lncs loebl logn lovasz luby mahajan maintain match matching matchings mathematics matrix maximal maximum mentioned method miller minors mohar morgan most mulmuley multiple naor naut nearly needs neighbour networks nonbipartite northholland note notes novick npcomplete number obvious onto open optimal orientations oriented ottawa oxford pages parallei parallel parfenoff part particular perfect permanent permanents permutation pfaffian pfaffians physics pippenger planar planarity plotkin plummer point polygonal polynomially polytope press problem problems proc proceedings process processors produces proof question ramachandran random recursively references reif related report reports representation respectively rounding routing runs rytter sahni schedul scheme science sciences search separator separators sequentially series shop show siam simon simple sinks small society solution some sources space spanning springer stacs stated stem step steps strongly structures sublinear subramanya subset such surface surfaces symposium synthesis system technical test testing that then theorem theoretic theoretical theory there think this thomassen time topological transactions tree trees unique university unmatched upfal using vaidya valiant vazirani verlag vertex vertices vinay volume weight whether which while white wigderson with work
http://doi.acm.org/10.1145/335305.335358	51	The Program-Size Complexity of Self-Assembled Squares	ability academy actuators adleman after already alternative always american annealing annual applications april arrays assembled assemblies assembly asymptotically automata based baum beginners bell bennett berger between bigger binding biological biomolecular biophysics bits blackwell blech bond both bowden brooklyn bulletin cahn cambridge cannot capillary carbeck case cell chemical choi circumvents column combinatorial comes complete complexity compressed computable computation computational computations compute computers computing conclusion considered constructions course crystal crystallography crystals decision design destroy destroyed device difference difficulty dimacs dimensional discussed discussion disintegration distinct domino dominoes each edition editor editors enzyme epitaxy exceeds expand experiments fact figure final forces from full functions fundamentals generalised generate genetic geometry gets give given global gratias growing growth gryzbowski halts hardly held hemaspaandra hexagonal hjelmfelt hosokawa however imperfect implementation instead integer interactions international into introduction inventiones involved itself journal june kari kinetics know kolmogorov kurtz labels landweber larger lateral length lett letters ligation limited lines lipton local logic long look looks lowest machine machines mackay magnasco mahaney main make makes manuscript markov math mathematical measure measures meeting memiors mesoscale metallic micro might minimum miura model molecular monotonic more nanotechnology national nature nonperiodicity novel nucleation number object objects only oooo order ordered orientational other ought output pages paper pattern pennsylvania perhaps phase phys physica physical physics plane plates polytechnic power preliminary press problem problems proceedings produce program providence proving ptashne quasicrystals radin rado random range recognition references region relevant remarkably required respect result resulting results retrospective review rnase robinson ross rothemund royer rubin schectman science sciences scientific second seeman select self selman senechal sensors shimoyama side similar simon simple simulate simulated simulations since singapore size society solutions some sources specificity specify springer square squares structure subset such surface surprising survive switch symmetry synthesis system technical template temporary tension terfort term than that then theochem theorems theoretical theory thermodynamics this thus tile tiles tilings toward translational turing turn types undecidability uniquely universal university unpublished until used using usual verlag vitanyi volume wang water wenzler where whereas while whitesides will winfree with wood words workshop world yang york
http://doi.acm.org/10.1145/335305.335332	24	Sharing the Cost of Multicast Transmissions	agent agents aggregation alamitos algorithm algorithmic algorithms allocation allocations allochtion among amsterdam artificial aspects assignment auctions automated ballardie berlin cambridge characterization choice compatibility compatible competitive computer computers computing conference contributions control controls conventions costs counterspeculation course crowcroff decentralized design designing diot draft economic economics efficient encounter finance flow game games greed green groves holland ieee ietf implementable incentive incentives information intelligence internal international internet joint journal lecture ledyard making management market maufer mechanism mechanisms minneapolis minnesota multi multicast negotiation network networking networks nisan north northholland notes osborne overhead performance perlman person preferences press pricing princeton principles proceedings progress protocol rate revelation roberts ronen rosenschein rubinstein rules sanders science sealed selfish shapley shenker shoham shubik simple since society springer symposium systems task tenders theoretical theory third transactions university users value verlag vickrey walsh wang wellman with work york zlotkin
http://doi.acm.org/10.1145/335305.335350	43	Tighter Lower Bounds for Nearest Neighbor Search and Related Problems in the Cell Probe Model	academic access adaptive addison agarwal ajtai algorithm algorithms alon amer analysis appear applications approach approximate april arrangements arya ashley asymmetric august automatic azuma barkol based beame beis berg boolean borodin bound bounds branching cell chakrabarti chazelle claim clarkson classification closest communication comp complexity compression comput computation computational computer conf consider content cost cover curse data database databases deerwester dense dept determinism devroye dimension dimensional dimensionality dimensions discovery discriminant discrimination dobkin duda dumais efficient entries every exists fagin features february find fixed flickner focs fraction furnas fuzzy general geometric geometry gersho good gorkani gray hafner half halfspaces handbook hard harshman hart hastie have hence high holland huang hyperplanes ieee image indexing indyk inequality info information international into israel jain kanal kleinberg kluwer knowledge kreveld krishnaiah kushilevitz landauer large latent learning least lemma less linear linearityofexpectation lipton location loth lowe lower lvov mach machine machines manipulation manuscript master matou matrices matrix meiser method methods miltersen mining model monochromatic most motwani mount multidimensional multimedia nearest nearestneighbor nearly neighbor neighbors netanyahu niblack nisan nondeterminism north number optimal ostrovsky overmars parametric partition patt pattern pentland petkovic photobook picard pods point points preprint probabilistic probe problems proc processing programs proof prove proximity qbic quantization queries query rabani rams random randomized ready recog reduction references related removing reporting retrieval richness safra saks salton salzberg sawhney scene schwarzkopf science sclaroff search searching semantic sets shape shooting should show siam signal silverman since size smeulders soda sorted space spaces specified spencer spie splitfind springer statistics steele stoc storage structures such sufficiently symbolic system systems tables technion technique techniques text than that thathachar theorem there therefore thesis tibshirani tighter time tools towards tradeoffs union using vector versus video vision wagner weighted wesley which widgerson wiley with workshop yanker zero zeros
http://doi.acm.org/10.1145/335305.335387	68	Parallelization, amplification-, and exponential time Simulation of quantum interactive proof systems	advances aharonov algebraic algorithms alizadeh analysis annual appeared applications babai barenco bennett bernstein berthiaume bounded boyd cambridge ceedings church circuit circuits classification cleve coins combinatorial combinatorica complete complexity computation computational computations computer computing condon conference consequences constant correction cryptographic density deterministic deutsch discrete distinguishability divincenzo editor editors eighteenth elementary ellipsoid ensembles error exponential factorization fault feige fidelity fifth fortnow foundations fourth fuchs fully gate gates given goldreich goldwasser graaf group grstschel having hemaspaandra horn hughston ieee information ings interactive interior johnson journal jozsa karloff kitaev knowledge lapidot letters lipton logarithms london lund margolus mathematical matrix measures mechanical method methods micali mixed modern multi networks nexp nisan nual optics optimization pages parallelized physical physics point polynomial power preliminary press prime principle private probability problems proceed proceedings programming proof protocols prover provers pspace public quantum rackoff randomness references research retrospective review round royal russian schrijver science selman semidefinite seventeenth shamir shor shot siam sipser sixth sleator smolin society springer springerverlag states structure success surveys symposium systems taxonomy their theory thirti time tolerant trading transactions turing twenty universal university vandenberghe vazirani version versus volume watrous weinfurter with wootters
http://doi.acm.org/10.1145/335305.335330	22	On Transformations of Interactive Proofs that Preserve the Prover's Complexity	about absolute abstract access achieving acknowledgments addressed advanced advances algebraic also annual another applications arora arranging arthur arvind assumption assumptions atlanta august babai baltimore beach been bellare between black bler boppana both bounded chicago circuits classes coin coins collapse collapses comparing complete completeness complexity comput computational computations computer computing conclusion conference consequences considered construct construction contribution control convert converting crypto cryptography cryptology current dallas damgfird decide decision deficiencies demonstrates derandomizing design desirable determine different direct discussions dishonest does easier editor editors eighth entropies equals eurocrypt even everything example exponential extended february first florida fortnow foundations fourteenthannual from ftirer full function functions games general generator give given goldreich goldwasser graph grateful hardness hashing have help hfistad hierarchy hitting honest ieee illinois illuminating impagliazzo implemented information institute insufficient interactive interest interesting into intractability issue issues journal karloff kilian klivans knowledge lacking language languages lecture lemma letters levin limits lncs looking luby lund main makes mansour many maryland massachusetts measure melkebeek membership menezes merlin methods miami micali miltersen minimum moran more multi namely naor nature necessary needed ninth nisan nonisomorphism notes nothing okamoto ones oracle ostrovsky other pages paper paso pennsylvania perfect permutations philadelphia polynomial pomerance possible power preprint preserve preserving press presumably private privatecoin problem problems proceedings processing promise proof proofs properties property protocol provable prove prover pseudo pseudorandom pseudorandomness pspace public publiccoin rackoff random randomized randomness references reingold relationships remove requires research resource result results revisited robustly rogaway rudich sahai sahal sanjeev sciencd science search seattle second selman separating separation sets several shaft shamir short showing siam siamj simplifies sipser size slam society software some sort soundness sparked springer standard statements statistical strictly structure study subexponential such suggested symposium syst system systems techniques technology texas than thank thanks that their theorem theoretical theory there these thesis thirty this time topic transformation transformations true twentieth twenty under unless using vadhan validity vanstone venkatesan verifier verlag version versus vinodchandran visit volume washington where which while wigderson with without work would yacobi yield york yung zachos zero
http://doi.acm.org/10.1145/335305.335342	35	More General Completeness Theorems for Secure Two-Party Computation	abstract achieving advances adversary aiken among analysis appear applications assumptions asymmetric based basing beaver beimel berkeley between bits boolean brassard cachin cacm california canetti case certified channels chor coding coin commitment completeness composition computation computations computer computing condition conjugate contracts correct correlated crdpean crdpeau crypto cryptogate cryptographic cryptography cryptolib cryptology damg department disclosure discrete eecs efficiency efficient elec electronic equivalence even exchange exist extended fact february figure finally flavors flipping follows forbidden foundations founding from games general generate generates give goldreich harvard have html http ieee implement improvement inequality information institute interactive journal kilian kushilevitz laboratory lemma lempel line lncs mail malkin massachusetts mathematics memo micali model multi multiparty must nature news noisy nothing oblivious ostrovsky part party passive peau philby possibility press privacy private probability problem problems proceedings proof protocol protocols rabin randomized reducibility reduction reductions references report robert rogaway salvail satisfied science secrets secure security send series sicomp sigact signing sketch society solve some springer straightforward such suppose symposium tech technical technology telephone that then theorem theoretic theory there thesis this three transfer transfers ucsd university used using vainish version weak weakened wiesner with would zero
http://doi.acm.org/10.1145/335305.335411	84	Balanced Allocations: The Heavily Loaded Case	above account alamitos aldous algorithms allocated allocations always analysis annual appeared applying approach approximation assign assumption assymptotic asymetry azar balanced balancing ball balls barcelona batch beach because berkeley berlin besides bins both bound bounds broder bubley burlington calculate california canada ceedings chains chemoff choices city cking combining comput computer computing conclude consequence constraints coupling couplings czumaj december definition density department dependence dependent dobmshin dobrushin dubhashi dyer dynamictectmical editors equal estimated event fall february fight finite fixed following follows foundations france from fulfill generating group groups height helps ieee induction inria instead international into invariant invariants january jump karlin karpelevice larger layer least lecture left line load location locations luby manuscript march markov markovian mathematics meanfield miami mitzenmacher mixing montreal more most multiplying mutations negative notes number obtain october oflnformation otherwise pages path placed points possible power preliminary press probabilit probabilities probability problems proceedings process processes proving quebec queue queueing queues raab random randomization randomized ranjan rapid rapidly reached references report rolim round scheme science sdminaire selection september serna shortest shown simple slam society spain spfinger springerveflag states steger structures study suhov suitable symposium system taking technique techniques term than that theoretical theory there therefore these thesis this thus transmission transpositions university upfal upper verlag vermont version volume vvedenskaya walks with workshop would xvii yields york
http://doi.acm.org/10.1145/335305.335397	73	A Constant Factor Approximation Algorithm for a Class of Classification Problems	advanced algorithm algorithmic algorithms analysis annual applications approximate approximating approximation approximations arbitrary bartal belmont besag books boykov breiman charles classification computer computing conference cuts dirty discontinuities efficient energy fast fields foundations friedman graph gruia howard ieee improved international jerome julian karloff linescu markov methods metric metrics minimization multiway olga olshen pages pattern pictures probabilistic proceedings rabani ramin random recognition references regression richard science software spaces statist statistical stone symposium theory tree trees veksler vision volume wadsworth with workshop yair yuri yuval zabih
http://doi.acm.org/10.1145/335305.335322	16	The value of strong inapproximability results for clique	advanced aeta algorithm algorithms amortized appear applications approximate approximating approximation approximations blum bounds characterization chernoffhoeffding chromatic clique cliques coloring complexity computations computer computing conference construction cornput covering dept deterministic discrete each electrical engebretsen engineering excluding feige foundations function given goldwasser graph graphs guarantees halld hard hardness holmerin ieee improved independence independent institute integer interactive japan journal limited lovasz lovhsz manuscript mathematics mathernatica measure numbers oojf optimal packing pages paper partitioning probabilistic problem proc products programs proofs query raghavan randomized references report rsson safra samorodnitsky schmidt science sciences separately sets siam siegel srinivasan stad subgraphs subgroup survey symposium system szegedy technology theory thesis towards trevisan unified with within
http://doi.acm.org/10.1145/335305.335352	45	Faster Suffix Tree Construction with Missing Suffix Links*	access algorithm algorithms alphabets annual applications association automata baker bounds cambridge case classes colloquium computer computing congress constructing construction data development dietzfelbinger dynamic economical efficient farach fast foundations fredman functions generalization giancarlo gusfield hash hashing heide high ieee ifip international journal karlin karp komlos languages large line linear lower machinery mance matching matrices mccreight mehlhorn optimal parameterized park pattern perfect perfor press proceedings programruing rabin randomized references research rohnert science sciences sequences siam siegel sleator space sparse square storing strings structure suffix switching symposium system szemeredi table tarjan their theory time trade tree trees ukkonen universal university upper weiner with world worst
http://doi.acm.org/10.1145/335305.335406	81	A Proof of the Security of Quantum Key Distribution	above accepted according aforementioned against algorithms alice allowed alto amer amongst amplification appear appendix arbitrarily aspects assoc assume attack attacks august average averaged bangalore bases basis because becomes bennett bessette biham bits both bound bounded bounds boyer brackets brassard calculated calculation cambridge channel channels chapter chau check choices chooses codes coding coherent coin collective commitment communication comp comput computer computers computing conf conference conjugate consequently consider crypto cryptography cryptology deduce definition delta density depend deutsch discrete distances distribution does downconversion drop eavesdropping ekert equalities equation error errors eurocrypt evanston expanded experimental expression fact factor factorization first fixed fixes found from fuchs functions gallagher gisin give given graaf griffiths have hoeffding icll icti iczl ieee improving independently india inequalities information inside irlb irlbl itibi itlb jilil jour jozsa jrlb jtibt june know langlois large last lctl leave left lemma less liitkenhaus lncs logarithms loll long look macchiavello mass mayers mean measurement measurements more must namely need news noisy norm note number oblivious obtained once only optimal other otherwise over pages pain parameters parametric parity particular parties pass peau peres phys polynomial popescu possible practical press prime principle privacy private probability proc proceedings processing proof protocols provably proves public quant quantum random rate recall reducing references removing replacement replacing salvail sampling sanders sanpera scale scheme science security shall shor shot show siam sigact signal simple simplifying since smolin soon star strategy string strings subscript sums superfluous superscript symmetric symmetrization symp syrup systems taken talk terms test than that then theory there this those time tossing transfer unbreakable unchanged unconditional uniquely using value values variables when where which whose wiesner with without workshop would write zero
http://doi.acm.org/10.1145/335305.335335	27	Complete Characterization of Security Notions for Probabilistic Private-Key Encryption	access achieving adaptively advances advantage adversary advnm after against algonthm algorithm algorithms along also among analysis annual appear applications april assume attack attacking attacks averaging based been bellare between case ceedings chapter characterization choose chosen ciphertext ciphertexts ckoff class clearly coins commitment completes complexity computer computing concrete construct crypto cryptographic cryptography cryptology cryptosystems december decryption defined defining definition definitions degenerates desai dicrescenzo discussed dolev dummy dwork else encryption encryptwo equivalence essential failind feigenbaum ffar following follows formalize formalized foundations from function functions gain generator given gold goldreich goldwasser have impagliazzo implicitly implies indicate indistinguishability information ings input interactive ishai january jokipii journal katz knowledge krawczyk lecture lemma lemmas levin llft luby made malleable manuscript micali model modes moreover must naor negligible nind noninteractive notation note notes notion notions occur only operation oracle ostrovsky other otherwise outputs over pages pair parallel parse particular pointcheval possible preliminary press previously princeton probabilistic proceed proceedings proof proofs provably proven pseudorandom pseudorandomness public queries query rackoff ralia random recall references reich relation relations remainder return rogaway sahai scheme schemes science sciences section secure security sense setting siam simon simplicity sloan some spring springer state submits submitted succa susceptible symmetric symposium system tava technion that then theory there this time times tion trapdoor treatment trivially unforgeable uniform university usage used using valid vector verlag vind when whenever where which wiener will with writing yung zero zeroknowledge
http://doi.acm.org/10.1145/335305.338762	31	Hard-Potato Routing	aeampora algorithms analysis annual approximate architectures aroya arrays baran borodin busch communications comparison computation computer computing connection deflection deterministic dimensional discrete distributed editor eilam eleventh exact fast feige forward foundations function germany goodman greedy greenberg halevi herlihy hillis hotpotato ieee infocom international isaac journal july june kaklamanis kaufmann krizanc lauer lecture lightwave machine many mesh meshes models multihop networks newman notes pages parallel pittsburgh potato potential press proc proceedings processor rabani raghavan randomized references routing schieber schroder schuster science shah sharp siam sigact sigarch single society springerverlag store symposium systems target theory transactions velen volume wattenhofer
http://doi.acm.org/10.1145/335305.335363	55	F r o m P a r t i a l C o n s i s t e n c y to G l o b a l B r o a d c a s t *	adrian agreement algorithms altos amotz andrew anna annual april august binary brian british byzantine canada changing coan columbia computer computing continuum cynthia danny data distributed dolev dwork editors expedite extending failure fast faults february garay gears haifa honest information international israel journal juan june karlin kaufmann kenneth lamport lecture leslie letters lynch majority management manuscript marshall michael models morgan multiparty multivalued nancy notes november pages pease perry presence principles proc proceedings processing protocols publishers rabin raymond reaching references robert russell science secret segall series sharing shifting shmuel shostak sixth slam springer srikanth stoc strong symposium systems theory toueg turpin vancouver verifiable volume wdag with workshop zaks
http://doi.acm.org/10.1145/335305.335344	37	Tight(er) Worst-case Bounds on Dynamic Searching and Priority Queues	acta addition algorithms also andersson applications balanced beame boas boolean bound bounded bounds brodal brodnik case comput computational constant design deterministic dictionaries dietz efficient emde erode faster fich finger focs forest fredman fusion geometry ihler implementation informatica information insertion kaas less lett levcopoulos linear lncs logarithmic loglog lower math mehlhorn method miltersen multiplication multiplications munro necessary operations optimal order ordered overmars pages predecessor preserving priority problem proc query queue queues raman rams randomized references riis search searching shift siam soda some sorting space static stoc sublogarithmic sufficient surpassing syst than theoretic theory thorup time transdichotomous tree trees update upper using wads willard wise with without worst zijlstra
http://doi.acm.org/10.1145/335305.335307	1	Pseudo-Random Functions and Factoring	able advances advantage alexi algor algorithmic algorithms also angluin appear application applications april authentication biham bits blum boneh book books both brassard breaking called cambridge ceedings certain chaum choices chor colloquium combinatorics communication completes complexity composite comput computational computationally computer computerscience computing conclude conn construct construction constructions core crypto cryptographically cryptology cryptosystems cyptobytes decision dept diffie digitalized discussion does easier eccc ecccbooks efficient electronic encryption equal exactly factoring factorization factors finally fischlin foundations fragments from function functions future generalized generate generation generator given goldreich goldwasser hard hastad have haven hellman hides html http ieee impagliazzo indistinguishability info information institute integerfaetorization intractable keys laboratory least lecture letters levin lichtenstein luby micali modulo motwani must naor newyork note notes number odlyzko over parallel partial parts permutations plenum poly predicate preliminary preserving press princeton private probabilistic probability problem proc proceedings processing proof proofs provable pseudo pseudorandom public publication quadratic rabin raghavan random reductions references reingold report required requiring residue residues retrieves rivest scheme schnorr science sciences secret secure security sequence shared sherman short shub siam signatures simple springer springerverlag stoc strong stronger survey symposium synthesizers syrup systems tags tech technical terminology than that their then theorem theoretic theory therefore thesis third this trapdoor trier univ university unpredictability unpredictable value vazirani verlag versions weizmann which whole with yale
http://doi.acm.org/10.1145/335305.335336	28	On Zero-knowledge Proofs: "From Membership To Decision"	abadi assumptions bellare blum boyar check checking closure coin compcom complete complexity computational concealing constant crescenzo crypto cryptology darnga decision deficiencies defining demonstrating density design designing discreetly efficiently everything feige feigenbanm fiat flipping focs formula friedl from giving goldreich goldwasser hashing hiding hints icalp icics identity ieee image impagliazzo increased information interactive interactiveszk isaac journal kannan kilian knowledge lund membership micali monotone ogaway optimal oracle ostrovsky perfect persiano phone power practical previous proceedings programs proofs protocol protocols provable references resultcorrectness resultindistinguishable round rounds sakurai sakural santis shamir simplify spring stacs stad stoc that their using version while without work yung zero zeroknowledge
http://doi.acm.org/10.1145/335305.335317	11	A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions	algebra algorithm algorithmic algorithms anal appl application applications approximation bachem base based bixby blocktriangularization bombay breach canceling capacitated capacity certain channel circulation class combinatorial combinatorica computer computing conference connectivity consequences control convex convexity correlated cost cunningham decomposition department dependence diophantine discrete dulmage edge edmonds efficiency ellipsoid engineering equivalence extreme families faster fenchel fifth fleischer flow flows frank fujishige function functions general generalized generic geometric giles goemans gordon graphs grstschel hanani holland hoppe ibaraki improvements india indian information institute integer iwata karp korte lexicographically linear location lovg math mathematical matrices matrix matroid matroids mccormick membership mendelsohn method minimax minimization minimizing minimum model multigraphs multipleaccess murota nagamochi narayanan network nheim north oper optimal optimization order other over partial partitioned polyhedra polymatroid polymatroidal polymatroids polynomial problem problems proceedings programming programs properties queyranne quickest ramakrishnan random references region related relation report respect rounding sauer scaling schrijver science seventh shigeno siam similarity simultaneous sohoni sources springer state strongly structure structures study subgradients submitted submodular submodularity subsets symmetric symposium systems tamir tardos technical technique technology testing their theorem theoretical theory time topics topkis transformations transshipment tree type under unifying variables vector verlag weight with
http://doi.acm.org/10.1145/335305.335311	5	A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume	advances aleksandrov alexandrov algebra algorithm algorithms also analysis annals applications approximate approximating assume avriel bapat barvinok baxany berlin best birthday bodies both bound breach brunn cambridge carlo case certain choose claim clearly combinatorial complexity comput computational computer computing conditions conjecture connected convex correspondingly courant course decompose deduce deterministic difficult dimensions discrete discriminants dokl doubly dyer easily easy edmonds egorychev eigenvalue eigenvector encountered encyclopedia equations essays estimating exactly exponential extremum fact factor falikman fenchel first follow forms friedland frieze from functions furedi generalized geometric geometry gordon grstschel gurvits hall hanani have hufnagel imply implying indecomposability indecomposable induction inequalities interior interscience into jerrum john just karp kaxmarkar like linear linial lipton lovasz lower luby math mathematics matrices matrix matroids means methods minimizing minkowski mixed monte multiples nemirovskii nesterov nonlinear note omit ones optimization panov permanent permanents philadelphia point polyhedron polynomial positive possible potyhedra prentice preprint presented press problem problems proc proceeding programming proof proving quadratic random references russian same samorodnitsky sauer scaling schneider schrijver schsnheim science semidefinite several show siam sign similarly simple simplest simply since sinclair solution soviet springerverlag stochastic strongly structures studies submodular subsidiaxy substituting symp that their theorem theoretical theory there therefore these this thus time true tuple tuples university valiant vector volume volumes waerden ways which wigderson with within would wrong york zametki
http://doi.acm.org/10.1145/335305.335310	4	A New Algorithmic Approach to the General Lovfisz Local Lemma with Applications to Scheduling and Satisfiability Problems*	acyclic algorithm algorithmic algorithms alon amsterdam applications applied approach approaches approximation asano aspects beck better birthday bound bounded bounds broadcast broder carnegie chapter chernoffhoeffding chromatic coloring colouring combinatorial combinatorica combinatorics computation computer computing congestion czumaj degree deterministic dilation dimensions discrete dynamic editors elsevier expander extension fast feige ffiredi finding finite focs foundations framework frieze frugally further general goemans goldberg good graham graph graphs grstschel guarantees hajnal handbook hind hirata holland hori hybrid hypergraph hypergraphs ieee improved independence infinite integer isaac isfiability jobshop john johnson journal kahn latin leighton lemma limited linial local lopsided loth lower maggs mathematics maximum mcdiarmid mellon method methods minmax molloy north order ordered packet pages parallel partitioning paterson path paul peleg pittsburgh probabilistic problem problems proc programming proofs provably questions radhakrishnan radio rado raghavan random randomized reed references related report results richa rounding routing satisfiability schedules scheduling scheideler schmidt school science selection semidefinite sets shmoys shop siam siegel soda some sons spencer srinivasan static stein steps stoc structures sweedyk symp syrup system technical technique theoretical theory thompson transversals uniform university upfal using version walk wein wiley williamson with yannakakis york
http://doi.acm.org/10.1145/335305.335359	52	Shortest Path Queries in Planar GraphsDannyZ. Chen and JinhuiXW Departmentof Computer Science and Engineering	advanced aigorithmica algorithmica algorithms analysis ancestors annual appl approach based clustering colloquium common communication comp compact complexity comput computation computer computing conf conference coyle data databases decomposable dept design designing digital dissertation effective engineering faster fibonacci finding fragmentation frederickson fredman geographic graph graphs heaps hershberger hierarchical huang improved information international intervals ivhs janardan jing journal kirousis klein knowledge kohli kozen kranakis krizanc leton lipton lowest maintenance management materialized math matrix message metric michigan model navigation network networks ofacm optimization pact parallelization path planar press proc proe queries query rauch references road route routing rundensteiner schieber science searching semi separator shekhar shortest siam simplification spaceefficient springer structure subramanian suri symp syrup systems table tables tarjan their theorem theory transportation traveler types univ university urrutia uses verlag view views vishkin with workshop
http://doi.acm.org/10.1145/335305.335316	10	Statistical Mechanics, Three-Dimensionality and NP-completeness * I. Universality of Intractability for the Partition Function of the Ising Model Across Non-Planar Lattices	academic addison aspects barahona baxter biggs body brandais brush camb cambridge camp classical colouring combinatorial complexity computational computing conjecture counting critical crystal cybernetics decay dimensional dimer disorder domb dorfman engr eulerian exactly fermion ferromagnet ferromagnetism feynman finding fisher from fromal georgii gibbs glass goodman graph graphs green gruyter hadlock harary harvard hedetniemi history holland institute interaction introduction ising journal knots kramers lectures lenz lovasz many matching math mathematical matrix maximum mccoy measures mechanics model models modern montroll montrou newell north onsager order orlova pages paths peierls phase phenomena phil phys physica physical physics planar plummer polynomial press problem problems proe references reviews sherman siam simple simplification solution solved some spin statistical statistics still summer superfluidity systems temperley theoretical theory thrive time transfer transition transitions treatment twodimensional university walks wannier ward welsh wesley with
http://doi.acm.org/10.1145/335305.335331	23	On the Sum-of-Squares Algorithm for Bin Packing	alamitos albers algorithms analyses analysis annual appear appeared applied average behavior best between biased case coffman communication comput computer computing continuous courcoubetis disc discrepancies discrete distributions fast first foundations functions fundamental garey ieee industrial item items johnson kenyon line linear lyapunov math mathematics matrix mcgeoch mitzenmacher multiplication ninth oper optimal packing packings pages perfect personal philadelphia preliminary press proc proceedings programming rabani random references rhee same science seventh shor shot siam sinclair size sizes society speeding stochastic symposium talagrand theorems theory title under using vaidya version walks weber wilson with yannakakis york
http://doi.acm.org/10.1145/335305.335329	21	A PCP Characterization of NP with Optimal Amortized Query Complexity	algorithms almost also amortized applications approximability approximating approximation arora aspects assignment bellare bits blum boolean ceedings characterization checkable checking classification complete complexity computational computer computing constant constraint correcting degree derived discrete efficient errata error european finding focs foundations free from gadgets goldreich goldwasser hardness ieee improved integer involving journal khanna linear linearity lncs luby lund maximization most motwani news nonapproximability numerical pages parallel pcps positive preliminary probabilistic probabilistically probability problems proc proceedin proceedings proe programming proof proofs queries query recycling references restricted results rubinfeld russell safra satisfaction satisfiability satisfiable satisfying science selftesting serna sheet siam sigact sorkin springer stoc sudan symposium syntactic szegedy test testing tests theoretical theory three tight towards trevisan variables vazirani verification verlag version versus views wards williamson with xhafa zwick
http://doi.acm.org/10.1145/335305.335371	60	A Matter of Degree: Improved Approximation Algorithms for Degree-Bounded Minimum Spanning Trees	able akademmi algorithms andrew another application approximating approximation april architecture area balaji bauer best bigger birds buffers california casting cheriyan chopra combinatorial company completeness computer computers computing constrained contradiction copy cornell crowder cruz deering degree department dept doklady editor engineering equality estrin extremum farinacci feasible fiirer fischer floyd follows framework framing francisco freeman from garey general gsia hall hard harlan have held hochbaum hunt integer intractability ithaca jacobson johnson journal karp khuller klein large last lecture letters level lightweight maccanne many marathe martin math mathematical method michael minimum modify multi multicast multiobjective nauk neal nearly nemhauser network networking networks node nodes notes november obtain operations optimal optimality optimization optimizing optimum order pages part philip point polyak polyhedron possible prentice presence problem problems proceedings programming proved publishing raghavachari ramming ravi references reliable report research rosenkrantz routing salesman samir santa scale science sessions shared sigcomm small solution solving spanning sssr steiner stone subgradient such switching symposium tanenbaum technical than that theory this transactions traveling tree trees ucsc uide university validation varma weight weighted wide wiley with within wolfe wolsey young zhang zhong
http://doi.acm.org/10.1145/335305.335394	71	Quantum lower bounds by quantum arguments	algorithm algorithms also ambainis archive arxiv august available beals bennett bernstein better bound bounds brassard buhrman classical cleve collision column communication complexity computation computer computing cryptology database error fast focs grover hayer journal list london lower mathematical mechanical mosca news ordered pages philosophical physical polynomials preprints problem proceedings quant quantph quantum references royal sampling schulman sciences search searching series shma siam sigact small society stoc strengths symposium tapp theory transactions vazirani weaknesses wigderson wolf zalka zero