Automata, Languages and Programming

Inhaltsverzeichnis

• Invited Lectures.
• Ushering in a New Era of Algorithm Design.
• A “proof-reading” of Some Issues in Cryptography.
• Credentials-Based Authorization: Evaluation and Implementation.
• Subexponential Parameterized Algorithms.
• Session A1.
• Competitive Algorithms for Due Date Scheduling.
• Mechanism Design for Fractional Scheduling on Unrelated Machines.
• Session A2.
• Estimating Sum by Weighted Sampling.
• Sampling Methods for Shortest Vectors, Closest Vectors and Successive Minima.
• Session A3.
• Low Distortion Spanners.
• Minimum Weight 2-Edge-Connected Spanning Subgraphs in Planar Graphs.
• Labeling Schemes for Vertex Connectivity.
• Session A4.
• Unbounded-Error One-Way Classical and Quantum Communication Complexity.
• A Lower Bound on Entanglement-Assisted Quantum Communication Complexity.
• Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.
• Session A5.
• An Optimal Decomposition Algorithm for Tree Edit Distance.
• On Commutativity Based Edge Lean Search.
• Commitment Under Uncertainty: Two-Stage Stochastic Matching Problems.
• Session A6.
• On the Complexity of Hard-Core Set Constructions.
• Approximation by DNF: Examples and Counterexamples.
• Exotic Quantifiers, Complexity Classes, and Complete Problems.
• Session A7.
• Online Conflict-Free Colorings for Hypergraphs.
• Distributed Computing with Advice: Information Sensitivity of Graph Coloring.
• Session C1.
• Private Multiparty Sampling and Approximation of Vector Combinations.
• Constant-Round Private Database Queries.
• Session A8.
• Universal Algebra and Hardness Results for Constraint Satisfaction Problems.
• On the Power of k-Consistency.
• Complexity of Propositional Proofs Under a Promise.
• Session C2.
• Deterministic History-Independent Strategies for Storing Information on Write-OnceMemories.
• Trading Static for Adaptive Security in Universally Composable Zero-Knowledge.
• A Characterization of Non-interactive Instance-Dependent Commitment-Schemes (NIC).
• Session A9.
• Sharp Tractability Borderlines for Finding Connected Motifs in Vertex-Colored Graphs.
• Parameterized Algorithms for Directed Maximum Leaf Problems.
• Parameterized Approximability of the Disjoint Cycle Problem.
• Linear Problem Kernels for NP-Hard Problems on Planar Graphs.
• Session C3.
• Private Locally Decodable Codes.
• Hash Functions in the Dedicated-Key Setting: Design Choices and MPP Transforms.
• Unrestricted Aggregate Signatures.
• Ring Signatures of Sub-linear Size Without Random Oracles.
• Session A10.
• Balanced Families of Perfect Hash Functions and Their Applications.
• An Exponential Improvement on the MST Heuristic for Minimum Energy Broadcasting in Ad Hoc Wireless Networks.
• Session B1.
• Modular Algorithms for Heterogeneous Modal Logics.
• Co-Logic Programming: Extending Logic Programming with Coinduction.
• Session C4.
• Offline/Online Mixing.
• Fully Collusion Resistant Black-Box Traitor Revocable Broadcast Encryption with Short Private Keys.
• Session A11.
• Succinct Ordinal Trees Based on Tree Covering.
• A Framework for Dynamizing Succinct Data Structures.
• In-Place Suffix Sorting.
• Session B2.
• Maximal Infinite-Valued Constraint Languages.
• Affine Systems of Equations and Counting Infinitary Logic.
• Boundedness of Monadic FO over Acyclic Structures.
• Session A12.
• Strong Price of Anarchy for Machine Load Balancing.
• Efficient Algorithms for Constant Well Supported Approximate Equilibria in Bimatrix Games.
• Session B3.
• Equational Systems and Free Constructions (Extended Abstract).
• Categorical Views on Computations on Trees (Extended Abstract).
• Session A13.
• Holographic Algorithms: The Power of Dimensionality Resolved.
• Reconciling Data Compression and Kolmogorov Complexity.
• Size Competitive Meshing Without Large Angles.
• Session B4.
• A Fully Abstract Trace Semantics for General References.
• Aliased Register Allocation for Straight-Line Programs Is NP-Complete.
• Conservative Ambiguity Detection in Context-Free Grammars.
• Session A14.
• Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming.
• Streaming and Fully Dynamic Centralized Algorithms for Constructing and Maintaining Sparse Spanners.
• Checking and Spot-Checking the Correctness of Priority Queues.
• Session B5.
• Undecidability of 2-Label BPP Equivalences and Behavioral Type Systems for the ?-Calculus.
• Ready Simulation for Concurrency: It’s Logical!.
• Continuous Capacities on Continuous State Spaces.
• Session A15.
• On the Chromatic Number of Random Graphs.
• Quasi-randomness and Algorithmic Regularity for Graphs with General Degree Distributions.
• Complexity of the Cover Polynomial.
• Session B6.
• A Generalization of Cobham’s Theorem to Automata over Real Numbers.
• Minimum-Time Reachability in Timed Games.
• Reachability-Time Games on Timed Automata.
• Perfect Information Stochastic Priority Games.
• Session B7.
• Bounded Depth Data Trees.
• Unranked Tree Automata with Sibling Equalities and Disequalities.
• Regular Languages of Nested Words: Fixed Points, Automata, and Synchronization.
• A Combinatorial Theorem for Trees.
• Session B8.
• Model Theory Makes Formulas Large.
• Decision Problems for Lower/Upper Bound Parametric Timed Automata.
• On the Complexity of Ltl Model-Checking of Recursive State Machines.
• Paper Retraction.
• Paper Retraction: On the Hardness of Embeddings Between Two Finite Metrics.