Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias
Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, Part I
ICALP (1), 2014.

@proceedings{ICALP-v1-2014,
	address       = "Copenhagen, Denmark",
	doi           = "10.1007/978-3-662-43948-7",
	editor        = "Javier Esparza and Pierre Fraigniaud and Thore Husfeldt and Elias Koutsoupias",
	isbn          = "978-3-662-43947-0",
	publisher     = "{Springer International Publishing}",
	series        = "{Lecture Notes in Computer Science}",
	title         = "{Proceedings of the 41st International Colloquium on Automata, Languages, and Programming, Part I}",
	volume        = 8572,
	year          = 2014,
}

Contents (89 items)

13 ×#graph
11 ×#algorithm
8 ×#performance
7 ×#bound
7 ×#on the
6 ×#approximate
6 ×#complexity
6 ×#problem
5 ×#game studies
4 ×#query

ICALP-v1-2014-GafniH

Sporadic Solutions to Zero-One Exclusion Tasks (EG, MH), pp. 1–10.

ICALP-v1-2014-Kuncak #recursion #verification

Verifying and Synthesizing Software with Recursive Functions — (Invited Contribution) (VK), pp. 11–25.

ICALP-v1-2014-AaronsonABB

Weak Parity (SA, AA, KB, MB), pp. 26–38.

ICALP-v1-2014-AbboudWW #performance #sequence

Consequences of Faster Alignment of Sequences (AA, VVW, OW), pp. 39–51.

ICALP-v1-2014-AbrahamC #distance

Distance Labels with Optimal Local Stretch (IA, SC), pp. 52–63.

ICALP-v1-2014-AdjiashviliBWZ

Time-Expanded Packings (DA, SB, RW, RZ), pp. 64–76.

ICALP-v1-2014-AfshaniCT #ram

Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM (PA, TMC, KT), pp. 77–88.

ICALP-v1-2014-AllamigeonBG #algorithm #game studies #polynomial

The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average (XA, PB, SG), pp. 89–100.

ICALP-v1-2014-AmbainisBGMSZ #complexity #metric

Tighter Relations between Sensitivity and Other Complexity Measures (AA, MB, YG, JM, XS, SZ), pp. 101–113.

ICALP-v1-2014-AmirCLL #on the

On Hardness of Jumbled Indexing (AA, TMC, ML, NL), pp. 114–125.

ICALP-v1-2014-AngeliniLBFPR #graph

Morphing Planar Graph Drawings Optimally (PA, GDL, GDB, FF, MP, VR), pp. 126–137.

ICALP-v1-2014-BaswanaK #algorithm #graph #incremental #maintenance

Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs (SB, SK), pp. 138–149.

ICALP-v1-2014-BavarianGI #communication #on the

On the Role of Shared Randomness in Simultaneous Communication (MB, DG, TI), pp. 150–162.

ICALP-v1-2014-Ben-SassonV #query

Short PCPs with Projection Queries (EBS, EV), pp. 163–173.

ICALP-v1-2014-BevernBBCFNW #graph

Star Partitions of Perfect Graphs (RvB, RB, LB, JC, VF, RN, GJW), pp. 174–185.

ICALP-v1-2014-BhattacharyaKM #coordination

Coordination Mechanisms for Selfish Routing over Time on a Tree (SB, JK, VSM), pp. 186–197.

ICALP-v1-2014-Biedl #graph #on the

On Area-Optimal Planar Graph Drawings (TCB), pp. 198–210.

ICALP-v1-2014-BjorklundH #polynomial

Shortest Two Disjoint Paths in Polynomial Time (AB, TH), pp. 211–222.

ICALP-v1-2014-BjorklundPWZ

Listing Triangles (AB, RP, VVW, UZ), pp. 223–234.

ICALP-v1-2014-BlaisHST #approximate #on the

On DNF Approximators for Monotone Boolean Functions (EB, JH, RAS, LYT), pp. 235–246.

ICALP-v1-2014-BringmannKPPT #performance #physics #simulation

Internal DLA: Efficient Simulation of a Physical Growth Model — (KB, FK, KP, UP, HT), pp. 247–258.

ICALP-v1-2014-BrietDHS #approximate #bound

Lower Bounds for Approximate LDCs (JB, ZD, GH, SS), pp. 259–270.

ICALP-v1-2014-CaiGW #algorithm #artificial reality

Holographic Algorithms Beyond Matchgates (JYC, HG, TW), pp. 271–282.

ICALP-v1-2014-CanonneR #probability #testing

Testing Probability Distributions Underlying Aggregated Data (CLC, RR), pp. 283–295.

ICALP-v1-2014-ChaillouxS #exponential #game studies #parallel

Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost (AC, GS), pp. 296–307.

ICALP-v1-2014-ChildsGW

The Bose-Hubbard Model is QMA-complete (AMC, DG, ZW), pp. 308–319.

ICALP-v1-2014-CleveM #constraints #game studies

Characterization of Binary Constraint System Games (RC, RM), pp. 320–331.

ICALP-v1-2014-ColeK #algorithm #performance #summary

Fast Algorithms for Constructing Maximum Entropy Summary Trees (RC, HJK), pp. 332–343.

ICALP-v1-2014-CzumajV #markov

Thorp Shuffling, Butterflies, and Non-Markovian Couplings (AC, BV), pp. 344–355.

ICALP-v1-2014-DattaHK #complexity #problem #reachability

Dynamic Complexity of Directed Reachability and Other Problems (SD, WH, RK), pp. 356–367.

ICALP-v1-2014-DemaineDFPSWW #assembly #simulation

One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile (EDD, MLD, SPF, MJP, RTS, AW, DW), pp. 368–379.

ICALP-v1-2014-DemaineHLS

Canadians Should Travel Randomly (EDD, YH, CSL, KS), pp. 380–391.

ICALP-v1-2014-DobzinskiL #performance

Efficiency Guarantees in Auctions with Budgets (SD, RPL), pp. 392–404.

ICALP-v1-2014-DregiL #complexity

Parameterized Complexity of Bandwidth on Trees (MSD, DL), pp. 405–416.

ICALP-v1-2014-DvirOS #equivalence #testing

Testing Equivalence of Polynomials under Shifts (ZD, RMdO, AS), pp. 417–428.

ICALP-v1-2014-DosaS #analysis

Optimal Analysis of Best Fit Bin Packing (GD, JS), pp. 429–441.

ICALP-v1-2014-ElkinNS

Light Spanners (ME, ON, SS), pp. 442–452.

ICALP-v1-2014-EmekR #set

Semi-Streaming Set Cover — (YE, AR), pp. 453–464.

ICALP-v1-2014-EsfandiariHKLMR #online #order #probability #scheduling

Online Stochastic Reordering Buffer Scheduling (HE, MH, MRK, VL, HM, HR), pp. 465–476.

ICALP-v1-2014-FeigeJ #preprocessor #query

Demand Queries with Preprocessing (UF, SJ), pp. 477–488.

ICALP-v1-2014-FialaKKN #algorithm #aspect-oriented #graph

Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs (JF, PK, JK, RN), pp. 489–501.

ICALP-v1-2014-BravermanG #bound

Public vs Private Coin in Bounded-Round Information (MB, AG), pp. 502–513.

ICALP-v1-2014-GavinskyL #reduction

En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations (DG, SL), pp. 514–524.

ICALP-v1-2014-GawrychowskiMW #matrix #query

Improved Submatrix Maximum Queries in Monge Matrices (PG, SM, OW), pp. 525–537.

ICALP-v1-2014-GilbertLPS

For-All Sparse Recovery in Near-Optimal Time (ACG, YL, EP, MJS), pp. 538–550.

ICALP-v1-2014-GolovnevKM #approach #problem #product line

Families with Infants: A General Approach to Solve Hard Partition Problems (AG, ASK, IM), pp. 551–562.

ICALP-v1-2014-GuptaTW #multi #optimisation

Changing Bases: Multistage Optimization for Matroids and Matchings (AG, KT, UW), pp. 563–575.

ICALP-v1-2014-HajiaghayiLP #algorithm #online #problem

Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems (MH, VL, DP), pp. 576–587.

ICALP-v1-2014-HegdeIS #linear #modelling

Nearly Linear-Time Model-Based Compressive Sensing (CH, PI, LS), pp. 588–599.

ICALP-v1-2014-Hertli #satisfiability

Breaking the PPSZ Barrier for Unique 3-SAT (TH), pp. 600–611.

ICALP-v1-2014-HsuRRU #linear #source code

Privately Solving Linear Programs (JH, AR, TR, JU), pp. 612–624.

ICALP-v1-2014-HohnMW #cost analysis #how #scheduling

How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions (WH, JM, AW), pp. 625–636.

ICALP-v1-2014-IaconoO #why

Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not (JI, ÖÖ), pp. 637–649.

ICALP-v1-2014-IshaiW

Partial Garbling Schemes and Their Applications (YI, HW), pp. 650–662.

ICALP-v1-2014-IvanyosKQSS #complexity #constraints #fault #on the #problem

On the Complexity of Trial and Error for Constraint Satisfaction Problems (GI, RK, YQ, MS, AS), pp. 663–675.

ICALP-v1-2014-Jakobsen

Information Theoretical Cryptogenography (SKJ), pp. 676–688.

ICALP-v1-2014-KhotTW #approximate #complexity

The Complexity of Somewhat Approximation Resistant Predicates (SK, MT, PW), pp. 689–700.

ICALP-v1-2014-KolMSY #approximate #bound #rank

Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound (GK, SM, AS, AY), pp. 701–712.

ICALP-v1-2014-KontogiannisZ #distance #network

Distance Oracles for Time-Dependent Networks (SCK, CDZ), pp. 713–725.

ICALP-v1-2014-KoppartyKS #finite #performance

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields (SK, MK, MES), pp. 726–737.

ICALP-v1-2014-KrawczykW #game studies #graph #online

Coloring Relatives of Interval Overlap Graphs via On-line Games (TK, BW), pp. 738–750.

ICALP-v1-2014-KumarS #bound

Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits (MK, SS), pp. 751–762.

ICALP-v1-2014-KusumotoY #morphism #testing

Testing Forest-Isomorphism in the Adjacency List Model (MK, YY), pp. 763–774.

ICALP-v1-2014-Lampis #approximate #graph #using

Parameterized Approximation Schemes Using Graph Widths (ML), pp. 775–786.

ICALP-v1-2014-LuWZ #fibonacci

FPTAS for Weighted Fibonacci Gates and Its Applications (PL, MW, CZ), pp. 787–799.

ICALP-v1-2014-BasavarajuFGMRS #algorithm

Parameterized Algorithms to Preserve Connectivity (MB, FVF, PAG, PM, MSR, SS), pp. 800–811.

ICALP-v1-2014-MakarychevM #clustering #graph

Nonuniform Graph Partitioning with Unrelated Weights (KM, YM), pp. 812–822.

ICALP-v1-2014-MakarychevP #scheduling

Precedence-Constrained Scheduling of Malleable Jobs with Preemption (KM, DP), pp. 823–834.

ICALP-v1-2014-MancinskaV #bound #probability

Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability (LM, TV), pp. 835–846.

ICALP-v1-2014-DapicMM #graph

QCSP on Semicomplete Digraphs (PD, PM, BM), pp. 847–858.

ICALP-v1-2014-MekaRRR #independence #performance #pseudo

Fast Pseudorandomness for Independence and Load Balancing — (RM, OR, GNR, RDR), pp. 859–870.

ICALP-v1-2014-MertziosNRS #interactive #memory management #network

Determining Majority in Networks with Local Interactions and Very Small Local Memory (GBM, SEN, CR, PGS), pp. 871–882.

ICALP-v1-2014-NelsonN #bound

Lower Bounds for Oblivious Subspace Embeddings (JN, HLN), pp. 883–894.

ICALP-v1-2014-OstrovskyPV #on the #proving

On Input Indistinguishable Proof Systems (RO, GP, IV), pp. 895–906.

ICALP-v1-2014-PrabhakaranSW #using

Secure Computation Using Leaky Tokens (MP, AS, AW), pp. 907–918.

ICALP-v1-2014-KlauckP #algorithm #interactive #problem #streaming

An Improved Interactive Streaming Algorithm for the Distinct Elements Problem (HK, VP), pp. 919–930.

ICALP-v1-2014-ReidlRVS #algorithm #performance

A Faster Parameterized Algorithm for Treedepth (FR, PR, FSV, SS), pp. 931–942.

ICALP-v1-2014-ReingoldRW #data type #graph #pseudo

Pseudorandom Graphs in Data Structures (OR, RDR, UW), pp. 943–954.

ICALP-v1-2014-Ben-SassonRTW #algorithm #proving

Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications (EBS, NRZ, MT, JW), pp. 955–966.

ICALP-v1-2014-Schmidt #sequence

The Mondshein Sequence (JMS), pp. 967–978.

ICALP-v1-2014-TalwarW #proving

Balanced Allocations: A Simple Proof for the Heavily Loaded Case (KT, UW), pp. 979–990.

ICALP-v1-2014-FouqueT #generative #random

Close to Uniform Prime Number Generation with Fewer Random Bits (PAF, MT), pp. 991–1002.

ICALP-v1-2014-TulsianiWZ #game studies #graph #parallel #rank

Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs (MT, JW, YZ), pp. 1003–1014.

ICALP-v1-2014-Tzameret #algorithm #problem #random #satisfiability

Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem — (IT), pp. 1015–1026.

ICALP-v1-2014-Volkovich #bound #learning #on the

On Learning, Lower Bounds and (un)Keeping Promises (IV), pp. 1027–1038.

ICALP-v1-2014-WangY #data type

Certificates in Data Structures (YW, YY), pp. 1039–1050.

ICALP-v1-2014-WimmerWZ #complexity #matrix #query

Optimal Query Complexity for Estimating the Trace of a Matrix (KW, YW, PZ), pp. 1051–1062.

ICALP-v1-2014-Wulff-Nilsen #approximate #distance #graph #performance

Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles (CWN), pp. 1063–1074.

ICALP-v1-2014-Yin #graph #random

Spatial Mixing of Coloring Random Graphs (YY), pp. 1075–1086.