Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I

Front Matter....Pages -
Sporadic Solutions to Zero-One Exclusion Tasks....Pages 1-10
Verifying and Synthesizing Software with Recursive Functions....Pages 11-25
Weak Parity....Pages 26-38
Consequences of Faster Alignment of Sequences....Pages 39-51
Distance Labels with Optimal Local Stretch....Pages 52-63
Time-Expanded Packings....Pages 64-76
Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM....Pages 77-88
The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average....Pages 89-100
Tighter Relations between Sensitivity and Other Complexity Measures....Pages 101-113
On Hardness of Jumbled Indexing....Pages 114-125
Morphing Planar Graph Drawings Optimally....Pages 126-137
Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs....Pages 138-149
On the Role of Shared Randomness in Simultaneous Communication....Pages 150-162
Short PCPs with Projection Queries....Pages 163-173
Star Partitions of Perfect Graphs....Pages 174-185
Coordination Mechanisms for Selfish Routing over Time on a Tree....Pages 186-197
On Area-Optimal Planar Graph Drawings....Pages 198-210
Shortest Two Disjoint Paths in Polynomial Time....Pages 211-222
Listing Triangles....Pages 223-234
On DNF Approximators for Monotone Boolean Functions....Pages 235-246
Internal DLA: Efficient Simulation of a Physical Growth Model....Pages 247-258
Lower Bounds for Approximate LDCs....Pages 259-270
Holographic Algorithms Beyond Matchgates....Pages 271-282
Testing Probability Distributions Underlying Aggregated Data....Pages 283-295
Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost....Pages 296-307
The Bose-Hubbard Model is QMA-complete....Pages 308-319
Characterization of Binary Constraint System Games....Pages 320-331
Fast Algorithms for Constructing Maximum Entropy Summary Trees....Pages 332-343
Thorp Shuffling, Butterflies, and Non-Markovian Couplings....Pages 344-355
Dynamic Complexity of Directed Reachability and Other Problems....Pages 356-367
One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile....Pages 368-379
Canadians Should Travel Randomly....Pages 380-391
Efficiency Guarantees in Auctions with Budgets....Pages 392-404
Parameterized Complexity of Bandwidth on Trees....Pages 405-416
Testing Equivalence of Polynomials under Shifts....Pages 417-428
Optimal Analysis of Best Fit Bin Packing....Pages 429-441
Light Spanners....Pages 442-452
Semi-Streaming Set Cover....Pages 453-464
Online Stochastic Reordering Buffer Scheduling....Pages 465-476
Demand Queries with Preprocessing....Pages 477-488
Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs....Pages 489-501
Public vs Private Coin in Bounded-Round Information....Pages 502-513
En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations....Pages 514-524
Improved Submatrix Maximum Queries in Monge Matrices....Pages 525-537
For-All Sparse Recovery in Near-Optimal Time....Pages 538-550
Families with Infants: A General Approach to Solve Hard Partition Problems....Pages 551-562
Changing Bases: Multistage Optimization for Matroids and Matchings....Pages 563-575
Near-Optimal Online Algorithms for Prize-Collecting Steiner Problems....Pages 576-587
Nearly Linear-Time Model-Based Compressive Sensing....Pages 588-599
Breaking the PPSZ Barrier for Unique 3-SAT....Pages 600-611
Privately Solving Linear Programs....Pages 612-624
How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions....Pages 625-636
Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not....Pages 637-649
Partial Garbling Schemes and Their Applications....Pages 650-662
On the Complexity of Trial and Error for Constraint Satisfaction Problems....Pages 663-675
Information Theoretical Cryptogenography....Pages 676-688
The Complexity of Somewhat Approximation Resistant Predicates....Pages 689-700
Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound....Pages 701-712
Distance Oracles for Time-Dependent Networks....Pages 713-725
Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields....Pages 726-737
Coloring Relatives of Interval Overlap Graphs via On-line Games....Pages 738-750
Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits....Pages 751-762
Testing Forest-Isomorphism in the Adjacency List Model....Pages 763-774
Parameterized Approximation Schemes Using Graph Widths....Pages 775-786
FPTAS for Weighted Fibonacci Gates and Its Applications....Pages 787-799
Parameterized Algorithms to Preserve Connectivity....Pages 800-811
Nonuniform Graph Partitioning with Unrelated Weights....Pages 812-822
Precedence-Constrained Scheduling of Malleable Jobs with Preemption....Pages 823-834
Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability....Pages 835-846
QCSP on Semicomplete Digraphs....Pages 847-858
Fast Pseudorandomness for Independence and Load Balancing....Pages 859-870
Determining Majority in Networks with Local Interactions and Very Small Local Memory....Pages 871-882
Lower Bounds for Oblivious Subspace Embeddings....Pages 883-894
On Input Indistinguishable Proof Systems....Pages 895-906
Secure Computation Using Leaky Tokens....Pages 907-918
An Improved Interactive Streaming Algorithm for the Distinct Elements Problem....Pages 919-930
A Faster Parameterized Algorithm for Treedepth....Pages 931-942
Pseudorandom Graphs in Data Structures....Pages 943-954
Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications....Pages 955-966
The Mondshein Sequence....Pages 967-978
Balanced Allocations: A Simple Proof for the Heavily Loaded Case....Pages 979-990
Close to Uniform Prime Number Generation with Fewer Random Bits....Pages 991-1002
Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs....Pages 1003-1014
Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem....Pages 1015-1026
On Learning, Lower Bounds and (un)Keeping Promises....Pages 1027-1038
Certificates in Data Structures....Pages 1039-1050
Optimal Query Complexity for Estimating the Trace of a Matrix....Pages 1051-1062
Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles....Pages 1063-1074
Spatial Mixing of Coloring Random Graphs....Pages 1075-1086
Back Matter....Pages -