Automata, languages, and programming : 41st international colloquium, icalp 2014, copenhagen, denmark, july 8-11, 2014, proceedings, part I / edited by Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, Elias Koutsoupias.

Springer eBooks

Invited Talks -- Sporadic Solutions to Zero-One Exclusion Tasks -- Verifying and Synthesizing Software with Recursive Functions (Invited Contribution) -- Track A: Algorithms, Complexity, and Games Weak Parity -- Consequences of Faster Alignment of Sequences -- Distance Labels with Optimal Local Stretch -- Time-Expanded Packings -- Deterministic Rectangle Enclosure and Offline Dominance Reporting on the RAM -- The Tropical Shadow-Vertex Algorithm Solves Mean Payoff Games in Polynomial Time on Average -- Tighter Relations between Sensitivity and Other Complexity Measures -- On Hardness of Jumbled Indexing -- Morphing Planar Graph Drawings Optimally -- Incremental Algorithm for Maintaining DFS Tree for Undirected Graphs -- On the Role of Shared Randomness in Simultaneous Communication -- Short PCPs with Projection Queries -- Star Partitions of Perfect Graphs -- Coordination Mechanisms for Selfish Routing over Time on a Tree -- On Area-Optimal Planar Graph Drawings -- Shortest Two Disjoint Paths in Polynomial Time -- Listing Triangles -- On DNF Approximators for Monotone Boolean Functions -- Internal DLA: Efficient Simulation of a Physical Growth Model [Extended Abstract]. Lower Bounds for Approximate LDCs -- Holographic Algorithms Beyond Matchgates -- Testing Probability Distributions Underlying Aggregated Data -- Parallel Repetition of Entangled Games with Exponential Decay via the Superposed Information Cost -- The Bose-Hubbard Model is QMA-complete -- Characterization of Binary Constraint System Games -- Fast Algorithms for Constructing Maximum Entropy Summary Trees -- Thorp Shuffling, Butterflies, and Non-Markovian Couplings.-Dynamic Complexity of Directed Reachability and Other Problems -- One Tile to Rule Them All: Simulating Any Tile Assembly System with a Single Universal Tile -- Canadians Should Travel Randomly -- Efficiency Guarantees in Auctions with Budgets -- Parameterized Complexity of Bandwidth on Trees -- Testing Equivalence of Polynomials under Shifts -- Optimal Analysis of Best Fit Bin Packing -- Light Spanners.-Semi-Streaming Set Cover (Extended Abstract) -- Online Stochastic Reordering Buffer Scheduling -- Demand Queries with Preprocessing -- Algorithmic Aspects of Regular Graph Covers with Applications to Planar Graphs -- Public vs Private Coin in Bounded-Round Information -- En Route to the Log-Rank Conjecture: New Reductions and Equivalent Formulations -- Improved Submatrix Maximum Queries in Monge Matrices -- For-All Sparse Recovery in Near-Optimal Time -- Families with Infants: A General Approach to Solve Hard Partition Problems -- Changing Bases: Multistage Optimization for Matroids and Matchings -- Problems -- Nearly Linear-Time Model-Based Compressive Sensing -- Breaking the PPSZ Barrier for Unique 3-SAT -- Privately Solving Linear Programs -- How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions -- Why Some Heaps Support Constant-Amortized-Time Decrease-Key Operations, and Others Do Not -- Partial Garbling Schemes and Their Applications -- On the Complexity of Trial and Error for Constraint Satisfaction Problems -- Information Theoretical Cryptogenography -- The Complexity of Somewhat Approximation Resistant Predicates -- Approximate Nonnegative Rank Is Equivalent to the Smooth Rectangle Bound -- Distance Oracles for Time-Dependent Networks -- Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields -- Coloring Relatives of Interval Overlap Graphs via On-line Games -- Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits.-Testing Forest-Isomorphism in the Adjacency List Model -- Parameterized Approximation Schemes Using Graph Widths -- FPTAS for Weighted Fibonacci Gates and Its Applications -- Parameterized Algorithms to Preserve Connectivity -- Nonuniform Graph Partitioning with Unrelated Weights -- Precedence-Constrained Scheduling of Malleable Jobs with Preemption -- Unbounded Entanglement Can Be Needed to Achieve the Optimal Success Probability -- QCSP on Semicomplete Digraphs -- Fast Pseudorandomness for Independence and Load Balancing [Extended Abstract] -- Determining Majority in Networks with Local Interactions and Very Small Local Memory -- Lower Bounds for Oblivious Subspace Embedding -- Secure Computation Using Leaky Tokens -- An Improved Interactive Streaming Algorithm for the Distinct Elements Problem -- A Faster Parameterized Algorithm for Treedepth -- Pseudorandom Graphs in Data Structures -- Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications -- The Mondshein Sequence -- Balanced Allocations: A Simple Proof for the Heavily Loaded Case -- Close to Uniform Prime Number Generation with Fewer Random Bits -- Optimal Strong Parallel Repetition for Projection Games on Low Threshold Rank Graphs -- Sparser Random 3-SAT Refutation Algorithms and the Interpolation Problem (Extended Abstract) -- On Learning, Lower Bounds and (un)Keeping Promises -- Certificates in Data Structures -- Optimal Query Complexity for Estimating the Trace of a Matrix -- Faster Separators for Shallow Minor-Free Graphs via Dynamic Approximate Distance Oracles -- Spatial Mixing of Coloring Random Graphs.

Para consulta fuera de la UANL se requiere clave de acceso remoto.