Meta tags:
Headings (most frequently used words):
2014, and, of, for, the, icalp, july, october, eatcs, guest, post, by, friday, in, nominations, day, wednesday, 11, 2015, call, andrew, winslow, 17, thursday, september, award, invited, talk, december, sunday, november, 08, 04, monday, 10, from, issue, bulletin, cfp, two, recap, networks, with, local, model, clément, canonne, amir, lewenstein, on, time, testing, conference, process, algebra, diary, 30, tuesday, 31, saturday, 03, august, 29, 13, 09, 07, pages, blog, archive, about, me, pc, chairs, 2016, reminder, deadline, several, awards, is, approaching, neat, problem, 1989, maths, olympiads, fellows, first, ccc, 15, posted, letter, president, presburger, distinguished, dissertation, report, trends, ilaria, castellani, mohammadreza, mousavi, recent, events, reykjavik, crossroads, art, science, 10th, ice, tcs, theory, george, mertzios, sotiris, nikoletseas, christoforos, raptopoulos, paul, spirakis, determining, majority, interactions, very, small, memory, karl, bringmann, fabian, kuhn, konstantinos, panagiotou, ueli, peter, henning, thomas, internal, dla, efficient, simulation, physical, growth, sanjeev, arora, abboud, virginia, vassilevska, williams, oren, weimann, consequences, faster, alignment, sequences, amihood, timothy, chan, moshe, noa, hardness, jumbled, indexing, john, iacono, özgür, özkan, why, some, heaps, support, constant, amortized, decrease, key, operations, others, do, not, victor, kuncak, andreas, björklund, thore, husfeldt, shortest, disjoint, paths, polynomial, mitsuru, kusumoto, yuichi, yoshida, forest, isomorphism, adjacency, list, rom, aschner, matthew, katz, bounded, angle, spanning, tree, modeling, angular, constraints, canal, tour, dinner, review, dnf, approximators, monotone, boolean, functions, eric, blais, welcome, claire, matthieu, györgy, dósa, jiří, sgall, optimal, analysis, best, fit, bin, packing, hossein, esfandiari, mohammadtaghi, hajiaghayi, reza, khani, vahid, liaghat, hamid, mahini, harald, räcke, online, stochastic, reordering, buffer, scheduling, erik, demaine, yamming, huang, chung, shou, liao, kunihiko, sadakane, canadians, should, travel, randomly, dmitry, gavinsky, shachar, lovett, en, route, to, log, rank, conjecture, new, reductions, equivalent, formulations, general, assembly, copenhagen, music, composed, gödel, prize, ceremony, gets, coverage, nature, fast, algorithms, constructing, maximum, entropy, summary, trees, howard, karloff, equivalence, polynomials, under, shifts, rafael, mendes, de, oliveira,
Text of the page (most frequently used words):
the (873), and (361), for (206), that (146), this (111), with (94), eatcs (78), 2014 (77), are (66), share (63), time (60), icalp (54), from (51), work (49), one (47), can (46), some (46), was (45), not (45), award (44), will (43), have (41), also (39), you (37), all (36), #problem (35), but (35), science (34), two (33), 2015 (33), talk (33), about (32), july (31), first (31), number (31), algorithm (31), email (29), they (27), has (27), research (26), october (25), december (25), posted (25), given (25), nominations (24), their (24), our (24), computer (24), luca (23), aceto (23), may (23), guest (23), post (23), comments (23), many (23), day (22), facebook (22), conference (22), algorithms (22), september (21), november (21), pinterest (21), blogthis (21), which (21), new (21), where (21), here (21), his (21), call (20), any (20), each (20), members (20), june (19), august (19), april (19), problems (19), tree (19), heaps (19), community (19), january (18), march (18), art (18), university (18), what (18), set (18), then (18), using (18), how (18), into (18), every (18), size (18), polynomial (18), theory (18), very (17), most (17), tcs (17), only (17), best (17), erik (17), must (17), february (16), presburger (16), good (16), graph (16), these (16), students (16), both (16), gave (16), known (16), boolean (16), computing (16), prove (15), had (15), paper (15), log (15), dnf (15), issue (14), other (14), there (14), nodes (14), well (14), function (14), pair (14), theoretical (14), andrew (13), people (13), committee (13), presented (13), out (13), process (13), used (13), case (13), learning (13), fellows (12), invited (12), model (12), such (12), after (12), bound (12), year (12), input (12), find (12), make (12), functions (12), who (12), more (12), monotone (12), http (12), like (12), field (12), org (12), winslow (11), bulletin (11), when (11), edges (11), three (11), over (11), them (11), possible (11), least (11), related (11), were (11), rank (11), protocol (11), track (11), mst (11), outstanding (11), prize (10), copenhagen (10), several (10), enjoy (10), networks (10), expected (10), total (10), fit (10), would (10), paths (10), between (10), been (10), theorem (10), testing (10), points (10), its (10), dissertation (10), candidate (10), microsoft (10), event (9), done (9), effect (9), scientists (9), data (9), results (9), large (9), including (9), graphs (9), ratio (9), use (9), achieve (9), lower (9), compute (9), conjecture (9), way (9), should (9), being (9), question (9), think (9), papers (9), node (9), 3sum (9), trees (9), look (9), key (9), equivalence (9), hope (9), scientific (9), mathematics (9), her (9), young (9), researchers (9), your (9), gödel (8), events (8), deadline (8), see (8), much (8), ceiling (8), local (8), few (8), properties (8), degree (8), considered (8), analysis (8), place (8), having (8), shortest (8), randomized (8), ideas (8), list (8), matrix (8), same (8), part (8), general (8), point (8), high (8), majority (8), linear (8), simple (8), hard (8), whether (8), might (8), even (8), following (8), summary (8), pit (8), ice (8), address (8), nomination (8), index (8), php (8), trends (7), distinguished (7), letter (7), 2016 (7), friday (7), read (7), colleagues (7), claire (7), glass (7), social (7), last (7), she (7), form (7), does (7), than (7), natural (7), bin (7), items (7), loglog (7), edge (7), while (7), demaine (7), none (7), within (7), constant (7), held (7), non (7), probability (7), too (7), approximation (7), writing (7), great (7), approach (7), takes (7), group (7), amir (7), important (7), thesis (7), dissertations (7), view (6), crossroads (6), cfp (6), technical (6), started (6), network (6), random (6), system (6), study (6), bins (6), item (6), instance (6), optimal (6), upper (6), type (6), randomly (6), uses (6), path (6), information (6), blocked (6), version (6), sqrt (6), selection (6), complexity (6), amount (6), japan (6), previous (6), end (6), working (6), dnfs (6), now (6), approximate (6), again (6), quite (6), whole (6), proof (6), rooted (6), different (6), www (6), available (6), program (6), did (6), whose (6), contributions (6), queries (6), others (6), decrease (6), academic (6), rule (6), please (6), colors (6), shape (6), speakers (6), future (6), concurrency (6), published (6), awards (6), access (6), 2013 (5), clément (5), recent (5), reykjavik (5), forward (5), thank (5), talks (5), chair (5), entitled (5), joint (5), why (5), incoming (5), according (5), above (5), better (5), giving (5), gap (5), fixed (5), take (5), either (5), times (5), comes (5), bounds (5), communication (5), inputs (5), bits (5), provide (5), assembly (5), kyoto (5), start (5), get (5), page (5), kindly (5), those (5), amongst (5), eric (5), computation (5), almost (5), open (5), blais (5), world (5), area (5), course (5), constraint (5), programming (5), next (5), example (5), just (5), long (5), spanning (5), additional (5), angle (5), give (5), tour (5), fellow (5), received (5), articles (5), interesting (5), modelling (5), string (5), alignment (5), since (5), preprocessing (5), query (5), result (5), fibonacci (5), roots (5), thursday (5), draw (5), entropy (5), decide (5), population (5), during (5), particle (5), peter (5), artistic (5), featured (5), presentation (5), association (5), lics (5), silicon (5), valley (5), 2010 (4), president (4), ccc (4), neat (4), maths (4), chairs (4), posts (4), danish (4), thanks (4), thore (4), husfeldt (4), looking (4), nature (4), homophily (4), week (4), david (4), scientist (4), authors (4), chosen (4), goes (4), class (4), final (4), really (4), online (4), opt (4), exist (4), instances (4), competitive (4), put (4), types (4), buffer (4), title (4), goal (4), tight (4), achieves (4), pseudo (4), until (4), main (4), combined (4), consider (4), minimum (4), value (4), proving (4), implies (4), rome (4), italy (4), submissions (4), years (4), far (4), issues (4), advisor (4), formulas (4), hypercube (4), written (4), subcubes (4), property (4), indeed (4), namely (4), computed (4), efficiently (4), approximated (4), strings (4), game (4), level (4), term (4), html (4), exists (4), tan (4), together (4), parity (4), requires (4), pdf (4), canonne (4), wednesday (4), specification (4), meets (4), job (4), four (4), programs (4), code (4), red (4), constraints (4), five (4), along (4), examples (4), vertices (4), disjoint (4), maximum (4), solving (4), cycle (4), andreas (4), leading (4), try (4), small (4), checking (4), omega (4), another (4), line (4), weight (4), hardness (4), common (4), through (4), second (4), unsupervised (4), topics (4), assuming (4), distribution (4), sanjeev (4), included (4), dictionary (4), substrings (4), quadratic (4), showed (4), histogram (4), lewenstein (4), mentioned (4), fast (4), pairing (4), sort (4), because (4), support (4), clique (4), third (4), named (4), rafael (4), efficient (4), state (4), shift (4), candidates (4), solve (4), before (4), karloff (4), include (4), applied (4), subject (4), scheduler (4), walk (4), thomas (4), organized (4), teaching (4), icelandic (4), attended (4), life (4), society (4), introduction (4), computational (4), message (4), excellent (4), robot (4), selected (4), behavioural (4), current (4), particular (4), automata (4), algebra (4), name (4), international (4), 31st (4), nominate (4), harvard (4), calls (4), reading (4), theme (3), complete (3), 2008 (3), 2011 (3), 2012 (3), music (3), composed (3), recap (3), report (3), ilaria (3), 1989 (3), olympiads (3), home (3), piece (3), ceremony (3), video (3), sub (3), further (3), twist (3), host (3), welcome (3), paris (3), monday (3), located (3), universities (3), hosting (3), female (3), entries (3), gives (3), men (3), top (3), 1000 (3), respectively (3), developed (3), formal (3), growing (3), means (3), added (3), repeatedly (3), advisors (3), attachment (3), defined (3), seems (3), sgall (3), standard (3), collection (3), placing (3), existing (3), otherwise (3), solution (3), old (3), sequence (3), steps (3), block (3), operation (3), adversarial (3), worst (3), models (3), regarding (3), solutions (3), attracted (3), compared (3), deterministic (3), improve (3), lead (3), difference (3), party (3), called (3), found (3), bit (3), bounded (3), equivalent (3), show (3), break (3), areas (3), representations (3), nice (3), yet (3), notion (3), furthermore (3), works (3), min (3), argument (3), cover (3), needed (3), help (3), concluded (3), approximating (3), someone (3), rocco (3), servedio (3), ever (3), probabilistic (3), via (3), needs (3), responsibility (3), victor (3), covered (3), performance (3), applications (3), structures (3), finally (3), based (3), major (3), run (3), vertex (3), self (3), permanent (3), running (3), asked (3), adjacent (3), isomorphic (3), visual (3), smallest (3), largest (3), family (3), distance (3), groups (3), dinner (3), author (3), role (3), turn (3), around (3), boundary (3), meeting (3), check (3), himself (3), develop (3), something (3), words (3), tractable (3), made (3), making (3), techniques (3), deep (3), human (3), pointed (3), learn (3), successfully (3), cases (3), abboud (3), williams (3), weimann (3), similar (3), usual (3), faster (3), clean (3), indexing (3), chan (3), positive (3), slides (3), audience (3), operations (3), pointer (3), build (3), children (3), john (3), moshe (3), max (3), standing (3), improving (3), big (3), mathematical (3), allow (3), combine (3), could (3), idea (3), vector (3), questions (3), correct (3), polynomials (3), prime (3), howard (3), distributed (3), rules (3), color (3), consisting (3), usually (3), containing (3), origin (3), idla (3), empty (3), location (3), session (3), paul (3), took (3), origami (3), cooperation (3), mit (3), systems (3), replicators (3), programme (3), instructions (3), impact (3), christian (3), robots (3), practice (3), protocols (3), challenges (3), authentication (3), established (3), recognize (3), phd (3), eligible (3), fields (3), sent (3), supervisor (3), letters (3), today (3), nominated (3), widmayer (3), supporting (3), encourage (3), submit (3), proceedings (3), importantly (3), kurt (3), position (3), sadoway (3), laboratory (3), usa (3), engineering (3), phone (3), journal (3), vicente (3), profile (2), 2006 (2), 2007 (2), 2009 (2), review (2), reminder (2), blog (2), archive (2), pages (2), gets (2), coverage (2), presenting (2), things (2), remember (2), opportunity (2), organizing (2), created (2), off (2), gmt (2), ens (2), watch (2), space (2), reports (2), mathieu (2), itu (2), separate (2), famous (2), database (2), authorship (2), subgraphs (2), women (2), assumptions (2), sufficient (2), imply (2), preferential (2), infinity (2), male (2), removing (2), dblp (2), intrinsically (2), hypothesis (2), meta (2), directly (2), formally (2), dösa (2), classic (2), packing (2), fewest (2), newly (2), room (2), placed (2), previously (2), shown (2), jiří (2), felt (2), vahid (2), liaghat (2), scheduling (2), enter (2), cost (2), processing (2), changes (2), esfandiari (2), designs (2), various (2), sizes (2), threshold (2), soon (2), specific (2), occurrences (2), traveler (2), partial (2), cannot (2), visited (2), parameterized (2), huang (2), liao (2), sadakane (2), ways (2), careful (2), yields (2), exactly (2), short (2), factor (2), dmitry (2), parties (2), blocks (2), below (2), polylog (2), gavinsky (2), lovett (2), led (2), involved (2), travel (2), kazuo (2), iwama (2), thought (2), matthieu (2), reductions (2), student (2), rich (2), wikipedia (2), faculty (2), mostly (2), 1999 (2), answered (2), bloggers (2), simplest (2), little (2), background (2), recall (2), arguably (2), everything (2), presence (2), hint (2), representation (2), fraction (2), order (2), negations (2), buy (2), surprising (2), asks (2), considering (2), clearly (2), shouldn (2), intuition (2), understand (2), huge (2), exponential (2), mind (2), exact (2), hastad (2), sampling (2), approximator (2), folklore (2), yang (2), typo (2), typesetting (2), synthesizing (2), focused (2), breaking (2), easier (2), doesn (2), briefly (2), arithmetic (2), algebraic (2), sat (2), integer (2), seconds (2), correctness (2), lines (2), black (2), combination (2), plus (2), fact (2), stressed (2), test (2), etc (2), trick (2), lists (2), especially (2), mention (2), length (2), minimizing (2), except (2), obstacle (2), relate (2), perhaps (2), already (2), probably (2), mitsuru (2), answering (2), setting (2), adjacency (2), matters (2), kusumoto (2), yoshida (2), forests (2), special (2), partitioning (2), ensures (2), aschner (2), katz (2), reduction (2), hamiltonian (2), square (2), step (2), larger (2), potential (2), connecting (2), resulting (2), ratios (2), awarded (2), moni (2), ronald (2), fagin (2), spoke (2), michael (2), successful (2), consecutive (2), rom (2), isomorphism (2), carry (2), execution (2), always (2), itself (2), intractability (2), statistical (2), right (2), starting (2), determining (2), realistic (2), subset (2), described (2), article (2), geometric (2), convex (2), polytope (2), obtained (2), contained (2), machine (2), approaches (2), evidence (2), matching (2), score (2), longest (2), subsequence (2), improvements (2), say (2), hugely (2), allowed (2), character (2), follow (2), produce (2), jumbled (2), alphabet (2), answer (2), occurrence (2), counts (2), naive (2), contribution (2), achieving (2), simultaneously (2), alphabets (2), timothy (2), mixing (2), kept (2), array (2), recommended (2), patrascu (2), left (2), note (2), iacono (2), özkan (2), without (2), pay (2), costs (2), distinct (2), elmasry (2), chain (2), remains (2), solvable (2), opening (2), refuting (2), strong (2), though (2), matter (2), task (2), project (2), instead (2), sure (2), anyway (2), went (2), weights (2), intuitive (2), prefixes (2), don (2), him (2), generalization (2), zero (2), improvement (2), matches (2), subroutine (2), parts (2), know (2), dvir (2), oliveira (2), shpilka (2), under (2), shifts (2), shirley (2), constructing (2), nlog (2), interaction (2), thing (2), seen (2), blue (2), endpoints (2), appear (2), basic (2), requirements (2), finite (2), mertzios (2), nikoletseas (2), christoforos (2), spirakis (2), fair (2), strictly (2), robust (2), karl (2), circles (2), radius (2), theta (2), bringmann (2), kuhn (2), panagiotou (2), jumps (2), leave (2), attending (2), lattice (2), internal (2), sunday (2), scs (2), centre (2), stage (2), however (2), showcasing (2), period (2), sciences (2), undergraduate (2), keynote (2), often (2), antithetic (2), artists (2), methods (2), intellectual (2), figures (2), renaissance (2), past (2), benefits (2), readers (2), artist (2), inspirational (2), anna (2), hrund (2), listening (2), interview (2), inspiration (2), fiction (2), answers (2), recently (2), swarms (2), multi (2), highlights (2), language (2), fun (2), masterclass (2), 2005 (2), whatever (2), eth (2), universidad (2), complutense (2), madrid (2), zoltan (2), esik (2), szeged (2), van (2), kim (2), larsen (2), aalborg (2), wang (2), mass (2), transformers (2), 10th (2), thinking (2), ccp (2), want (2), sense (2), school (2), edition (2), series (2), ifip (2), workshop (2), participants (2), passport (2), abstract (2), equivalences (2), verify (2), security (2), devised (2), associates (2), application (2), overview (2), link (2), logic (2), minimization (2), respect (2), notions (2), lts (2), motto (2), alexandra (2), mohammadreza (2), mousavi (2), castellani (2), defended (2), respective (2), euro (2), receiving (2), web (2), submitted (2), addition (2), endorsement (2), opinion (2), theses (2), fedor (2), fomin (2), date (2), department (2), european (2), conferred (2), annually (2), member (2), later (2), consists (2), justification (2), mail (2), woodruff (2), heart (2), favourite (2), researcher (2), truly (2), recipients (2), courses (2), enrollments (2), institutions (2), signed (2), substantial (2), let (2), enjoyed (2), willingness (2), publication (2), outlet (2), springer (2), hearing (2), publications (2), strongly (2), acm (2), prizes (2), achievement (2), spotlight (2), younger (2), worth (2), announce (2), distant (2), happy (2), institute (2), fundamental (2), staff (2), loss (2), positions (2), prestigious (2), honours (2), vladimiro (2), sassone (2), whet (2), appetite (2), anca (2), muscholl (2), bordeaux (2), france (2), individual (2), service (2), news (2), provides (2), leda (2), book (2), accept (2), desk (2), geometry (2), citizens (2), secretary (2), achievements (2), affiliation (2), postal (2), nominator (2), accomplishments (2), characteristics (2), reality (2), diary (2), awesome, inc, powered, blogger, 109, cere, andre, castel, disserta, oct, 2017, 2018, 2019, 2020, 2021, 2022, 2023, 2024, 2025, 2026, subscribe, atom, older, newer, composition, english, titles, adding, back, lovely, breathe, atmosphere, capital, city, saw, arriving, kongens, nytorv, smiling, guy, showing, sign, cyclists, car, drivers, husk, smuk, beautiful, trio, opened, legendary, 150, lunch, concert, launch, reception, meet, preparing, band, jazzy, relaxed, ambience, kicks, tomorrow, 30am, plenary, streamed, live, græd, recording, jazzhus, montmartre, jazz, festival, carsten, dahl, kicked, mentioning, stats, noted, conferences, month, denmark, emergence, chen, avin, zvi, lotker, barbara, keller, peleg, yvonne, ann, pignolet, asking, listed, rare, similarly, bleak, induced, shows, connected, disconnected, sparse, proved, minimal, iteratively, chosing, examining, said, parameters, able, verified, experimentally, modifying, account, capture, rather, proven, cause, struck, ness, isn, impacts, ability, specified, numbers, assign, permanently, differ, criteria, oldest, remaining, ceil, improved, dropping, completing, commented, deserved, agree, air, finality, rest, universe, sized, flushing, causing, processed, studies, sitation, sampled, average, adversary, permuted, lemmas, exceeded, curious, canandian, introduced, papadimitriou, yannakakis, 1991, intense, canadian, snowfall, traversed, endpoint, avoids, implied, nearly, traverse, repeating, reaching, destination, whereas, finds, reviewing, passing, entry, rectangles, partition, rectangular, versions, progress, low, ended, appearances, accomodations, statistics, elias, koutsoupias, acceptance, rate, steady, vast, bulk, organization, notch, sessions, sound, projection, existent, food, drink, tasty, rotates, shachar, route, formulations, yamming, chung, shou, kunihiko, canadians, hossein, mohammadtaghi, hajiaghayi, reza, khani, hamid, mahini, harald, räcke, stochastic, reordering, györgy, dósa, stick, gender, minority, richer, choose, proportional, inge, lehmann, swat, sea, building, parlance, 2000, concerned, precisely, disjunctive, normal, eactly, taking, union, prefers, argue, depth, nightmare, extensively, studied, amidst, facts, mere, auditorium, clear, settled, turns, picture, understood, required, allows, error, leads, brings, coordinate, wise, starter, intuitively, anything, suppose, approximations, gist, drastic, savings, maj, counting, concentration, measure, middle, belt, subcube, thus, lot, allowing, yep, currently, additionally, separation, boggling, changing, quantifiers, independent, fix, broken, columbia, edu, icalp14, upshot, independently, stitching, regularity, lemma, simpler, reduce, quine, friend, korshunov, kuznetsov, lupanov, johan, håstad, approximators, verifying, software, recursive, phillipe, suter, turning, scala, implemented, indicated, row, table, mean, easy, induction, reasoning, solvers, empirical, 100, counterexamples, incorrect, tress, insertion, encoded, elements, inserted, although, prototyping, generation, cool, counterexample, negation, reducing, verification, extreme, generating, converting, dates, sorted, impressed, floating, avoided, rounding, errors, winner, undirected, pairs, minimized, near, lengths, thrust, entirely, focusing, loops, journey, eliminated, certain, ring, necessary, replaced, determinant, computations, technique, followup, slide, prepared, conclusion, posed, direction, undireced, covers, cycles, divisible, introducing, correctly, 3rds, present, repesentation, performing, subgraph, significantly, away, partitions, nicely, wireless, design, plane, output, euclidean, equilateral, triangle, require, interior, simply, collinearly, apart, shared, causes, trivial, interval, finding, hexagonal, grid, greater, shorter, collections, enough, actually, reduced, pigeonhole, shofting, groupings, canals, odd, palace, historical, franklin, missing, fourth, facilitating, collaboration, naor, amnon, lotem, canal, connect, decompose, matthew, modeling, angular, yuichi, forest, björklund, leon, synthesis, create, assertion, compile, andrej, spielmann, ettienne, kneuss, eva, darulova, ruzica, piskac, kuncak, survey, provable, across, overcoming, refers, loosely, pile, raw, extra, relevant, newspaper, foothold, unknown, explanation, overcome, explained, lie, topic, corpus, text, york, describe, advance, separable, hull, removed, complex, objects, built, neutral, cortex, barrier, effective, effectively, trying, ouch, accuracy, rates, corpora, conditional, defining, symbols, maximizes, resisted, exponent, quick, genomic, heuristics, popular, slow, billion, edit, penalties, commen, wildcards, wildcard, characters, match, proofs, flavor, preprocess, pattern, suffix, arrays, yield, scanning, window, sum, precompute, histograms, unpublished, structure, motivation, details, convolution, indices, proves, hand, drawn, caught, beginning, deadpan, delivery, promise, keep, light, quiet, chuckling, chat, insert, extract, families, bigger, distingushes, augmentation, root, augmented, fredman, classes, assumption, values, requirement, restriction, says, nothing, cheat, height, actual, considers, grow, contradiction, recursively, repeat, attention, özgür, amortized, unlike, amihood, noa, resolving, cnf, solved, weak, blast, virginia, vassilevska, oren, consequences, sequences, arora, revolved, gigantic, tiny, sheet, screen, magnificent, weighted, parameter, genealogy, descendants, obscure, mathematician, gauss, hell, carefully, dismiss, subsets, naturally, assigning, straightforward, fashion, original, subtree, balanced, phrased, differently, arbitrary, metanode, slight, exponentially, possibilities, pretty, bad, decreasing, sadly, counter, managed, additive, came, kill, albeit, provably, greedy, crux, alright, sorting, merging, merge, yes, device, blackbox, variate, devices, coauthors, infamous, identity, affairs, ramifications, difficult, generalizes, explicit, witness, represented, coefficients, spite, harder, randomness, translates, corresponding, roughly, speaking, successively, coming, longer, alas, plug, collapse, forth, simplifications, trickles, down, calling, lets, hold, hop, graphics, forum, thumb, write, trap, cole, morally, zeev, mendes, voilà
Text of the page (random words):
a tractable subset by looking for realistic assumptions that lead to tractable instances as an example he described the topic modelling problem where one is given a corpus of text e g all new york times articles and the goal is to describe each article as a linear combination of topics where the topics are not given in advance i e unsupervised learning a geometric view of this problem is being given a set of points in a convex polytope articles and being asked to find the vertices of the polytope topics the problem is np hard in general but can be made tractable by assuming that the data is separable the vertices are included in the set of points given then a polynomial time algorithm have be obtained for each point test if it s contained on the convex hull if not it can be removed and otherwise it must be a vertex he also spoke about making process on other machine learning techniques including dictionary learning given complex objects built from a small simple dictionary compute the dictionary and approaches like deep learning many level neutral networks dictionary learning and deep learning are both thought to take place in the human visual cortex giving good evidence that their worst case intractability is not a barrier to their effective use for the case of deep learning sanjeev pointed out that learning the network is effectively trying to learn a tc 0 ouch and yet they have been used successfully by machine learning people to achieve high accuracy rates on large corpora amir abboud virginia vassilevska williams and oren weimann consequences of faster alignment of sequences amir gave this talk on conditional lower bounds on local matching a pair of strings given a function defining a score for every pair of symbols find a pair substrings from the input string that maximizes the score like other string problems including longest common subsequence the best known algorithm for local alignment takes quadratic time and has resisted improvements in the exponent to say o n 1 99 amir was quick to point out local alignment is hugely important in genomic sequence analysis heuristics like blast are hugely popular and that quadratic is too slow in these cases since n can be several billion abboud williams and weimann prove that a o n 2 ε time algorithm for local alignment implies the following results 3sum solved in o n 2 δ time for some δ refuting the weak form of the 3sum conjecture cnf sat solvable in o 2 δ n time refuting the strong exponential time hypothesis max 4 clique solvable in o n 4 δ time for some δ resolving a long standing opening problem of improving the best known algorithm for max 4 clique they also prove similar results for other problems including edit distance with gap penalties and longest commen subsequence with wildcards input strings are allowed to have wildcard characters that match any character the proofs follow the usual approach of using a o n 2 ε time local alignment algorithm to produce faster algorithms for the other problems and those that amir showed were very clean amihood amir timothy m chan moshe lewenstein and noa lewenstein on hardness of jumbled indexing this work has a similar flavor to the abboud williams weimann paper using the 3sum conjecture to develop lower bounds for string problems unlike that paper this work gives lower bounds for data structures answering queries the main problem considered is of jumbled a k a histogram indexing given a string t with alphabet of size k preprocess t to answer queries of the form what substrings of t have character occurrence counts i e what substrings have the given histogram for many pattern matching problems on strings suffix trees arrays are used to achieve linear time queries for histogram indexing naive approaches yield either o 1 preprocessing and o n query time scanning the string using a window whose size is the sum of the entries in the histogram or o kn 2 preprocessing time and o 1 query time precompute the histograms of all substrings and look up the answer the contribution of amir chan lewenstein and lewenstein is to prove that assuming the 3sum conjecture these results are the best possible for a fixed alphabet of size k at least 3 they prove that achieving o n 2 2 k preprocessing and o n 1 1 k query time simultaneously is 3sum hard for alphabets of non constant size they prove that achieving o n 2 ε preprocessing and o n 1 δ query time is 3sum hard he also mentioned that unpublished work with timothy chan achieves a positive result in the form of a data structure that achieves o n 2 2 k o 1 preprocessing and o n 1 1 k o 1 query time simultaneously for fixed alphabets moshe did a good job of mixing the problems motivation and technical details in a way that kept the talk interesting related to the reductions in this work which use a reduction from convolution 3sum testing whether there exist two indices i j of the input array such that a i a j a i j he also recommended that people read patrascu s paper that proves this special form of 3sum is 3sum hard john iacono and özgür özkan why some heaps support constant amortized time decrease key operations and others do not john s hand drawn slides caught the attention of some people from the very beginning and combined with his deadpan delivery and promise to keep it light left the audience quiet chuckling through the talk the talk started with a chat about heaps all good heaps have o log n time insert and extract min operations decrease key is also an operation of heaps some heaps are better at it there are three families of heaps with three different running times for decrease key fibonacci and improvements that achieve o 1 time pairing heaps that achieve o 2 2 sqrt loglog n time elmasry sort heaps that achieve o loglog n time all decrease key operations of these trees pair small trees into bigger trees what distingushes them is how they do this pairing heaps repeatedly pair trees recursively repeat until one tree remains elmasry sort heaps break roots into blocks of size log n chain all roots of a block together for fibonacci heaps pair heaps whose roots have the same number of children note that the fibonacci pair based on tree size not key value and use an augmentation of loglog n bits in each root seems like you augmented bits fast fredman considered this in 1999 proving o 1 decrease key implies omega loglog n bits for some classes of heaps namely pairing heaps but lower bound requires assumption that every time a pair of roots have their values compared their heaps are combined this contribution of iacono and özkan is a new lower bound without such the requirement that trees are combined when compared but with a new restriction must pay pointer model costs this result yields lower bound of omega loglog n for pairing and sort heaps but says nothing about fibonacci heaps because they cheat they do not pay pointer model costs a pointer model version would build a tree above the array which would have height loglog n and give decrease key a similar running time the actual proof is adversarial and considers a whole family of distinct fibonacci heaps that must grow larger than the total number of possible heaps a contradiction posted by luca aceto at 8 08 pm no comments email this blogthis share to x share to facebook share to pinterest icalp day 2 guest post by andrew winslow andrew winslow was one of the colleagues who kindly answered my call for guest bloggers from icalp 2014 here is guest post on the second conference day enjoy it invited talk victor kuncak victor gave a talk entitled verifying and synthesizing software with recursive functions about work with his students including ruzica piskac phillipe suter eva darulova ettienne kneuss and andrej spielmann the work focused on a number of problems in the area of turning a specification into a program that meets it he did a great job of breaking out four types of problems they re working on run time compile time have specification c and program p assertion checking check p meets c prove correctness prove p always meets c have specification c constraint programming carry out execution according to c program synthesis create p meeting c their work is done in scala and implemented in the leon system out of the four types of problems victor indicated that the first two first row of the table are easier of course easier doesn t mean easy and he briefly covered a few of the ideas induction arithmetic algebraic reasoning sat solvers integer linear programs used to achieve good empirical performance a few seconds to prove correctness programs of 100 lines of code or more and counterexamples in the case of incorrect code constraint programming was next and he gave the example of programming red black tress via constraints using as constraints the five properties a red black tree must have insertion for instance would be encoded as a combination of the five properties plus the fact that the new tree must have the elements of the old tree plus the inserted item although the performance was not great he stressed that the applications of constraint programming are more along the lines of prototyping new data structures test case generation etc one cool trick was using the fact that a solution is a counterexample of the negation of the constraints reducing the problem to one in program verification finally he covered most extreme problem writing code based on a specification here he had some really nice examples generating code for converting dates and times simple data structures like sorted lists etc in just a few seconds many ideas were used but i was especially impressed by his mention of their work on floating point representations synthesizing programs that avoided rounding errors andreas björklund and thore husfeldt shortest two disjoint paths in polynomial time andreas gave the talk for this best paper award winner in track a the problem considered is a very simple one given an undirected graph and two pairs of vertices s1 t1 and s2 t2 find a pair of disjoint paths whose total length is minimized several problems near to this one are np hard e g minimizing the maximum of the two path lengths so placing the problem into p is the major thrust of the paper the algorithms given run in o n 11 and o n 22 time for vertex and edge disjoint paths respectively the approach of the algorithm is almost entirely matrix based focusing on solving a cycle cover problem on the input graph with self loops added to each vertex except that doesn t quite work andreas did a great job of leading us on a journey where obstacle after obstacle to the approach was eliminated many of the issues relate to the complexity of computing permanent indeed one of the major technical contributions is proving that computing the permanent of a matrix over a certain type of ring is in p in the end the necessary permanent computation is replaced with a polynomial number of determinant computations giving the large but polynomial running time in perhaps the most natural course of events someone asked after the talk whether the technique might work for the shortest three disjoint paths so natural was the question that a followup slide for the question was already prepared the conclusion was probably not but andreas posed a first problem to try in this direction given an undireced graph compute the parity of the number of cycle covers having c cycles with c divisible by 4 mitsuru kusumoto and yuichi yoshida testing forest isomorphism in the adjacency list model mitsuru started by introducing the notion of property testing on graphs computing whether the graph has a given property answering correctly at least 2 3rds of the time while using only a small number of queries on the graph in this setting even the representation of a graph as an adjacency matrix or list matters as checking whether a given edge is present takes too long with an adjacent list repesentation kusumoto and yoshida considered the problem of testing whether two forests are isomorphic it was known that in general graphs this problem requires omega sqrt n queries to the graphs and only o 1 if the graphs have bounded degree for forests they achieve an algorithm that uses only o polylog n queries and prove omega sqrt log n are needed the algorithm works by first performing a special type of partitioning of the input graph then testing whether each subgraph is isomorphic the partitioning is done in a way that ensures that if the two input graphs are significantly far away from being isomorphic then some pair of their subgraphs in their partitions are too rom aschner matthew j katz bounded angle spanning tree modeling networks with angular constraints rom gave a nicely visual talk about a problem in wireless network design in the plane the input is a set of points and the output is a euclidean minimum spanning tree mst with an additional constraint the smallest angle spanning all of the edges is at most some fixed constant b a b mst another way to think about this constraint is that the largest angle between any pair of adjacent incoming edges must be at least 2 π b for b π 3 a b mst may not even exist three points at the vertices of an equilateral triangle require at least one of the points to have two incoming edges with interior angle π 3 for b 8 π 5 the b mst is simply the minimum spanning tree as the upper degree bound of 5 on every node in an mst ensures the smallest angle spanning all of the edges is at least 2 π 2 π 5 8 π 5 finally for b 1 2 there exists a simple family of examples n 1 points placed collinearly ε distance apart and a final point distance 1 from the shared line that causes the b mst to have total weight ε n 1 1 and b mst to have total weight 1 n 1 n 1 so the non trivial b are those in the interval 1 2 8 5 pi for these aschner and katz prove both np hardness and approximation results they prove that finding the b mst for b π and b 2 π 3 are both np hard using a reduction from hamiltonian path in square and hexagonal grid graphs respectively they also achieve constant factor approximation algorithms for b π 2 π 3 π 2 the approximation algorithms use a common sequence of steps compute the mst turn the mst into a hamiltonian cycle via a tour around the boundary of the mst decompose the points into consecutive groups along the cycle for each group compute a set of edges connecting the points and minimizing total edge length connect adjacent groups using the shortest edge possible step 4 requires a careful selection of group sizes as larger groups give greater potential for shorter collections of edges but for large enough b actually connecting the points may not be possible the resulting approximation ratios are 16 and lower and can further be reduced by a neat pigeonhole argument regarding shofting the groupings along the tour canal tour and conference dinner the day concluded with a tour through the canals of copenhagen and dinner at the odd fellow palace the 2014 gödel prize was awarde...
|
