Automata, Languages, and Programming 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I - neues Buch

EAN (ISBN-13): 9783662476710
ISBN (ISBN-10): 3662476711
Gebundene Ausgabe
Taschenbuch
Erscheinungsjahr: 2015
Herausgeber: Springer Berlin

Buch in der Datenbank seit 2015-08-23T23:55:10+02:00 (Zurich)
Detailseite zuletzt geändert am 2024-03-01T18:38:43+01:00 (Zurich)
ISBN/EAN: 9783662476710

ISBN - alternative Schreibweisen:
3-662-47671-1, 978-3-662-47671-0
Alternative Schreibweisen und verwandte Suchbegriffe:
Autor des Buches: kobayashi, speck, halldorsson, halldórsson, lauth, speckmann, magnus, kazuo
Titel des Buches: programming language, international colloquium, lecture notes computer science automata, kyoto japan, magnus

---

Daten vom Verlag:

Autor/in: Magnús M. Halldórsson; Kazuo Iwama; Naoki Kobayashi; Bettina Speckmann
Titel: Theoretical Computer Science and General Issues; Lecture Notes in Computer Science; Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I
Verlag: Springer; Springer Berlin
1111 Seiten
Erscheinungsjahr: 2015-07-06
Berlin; Heidelberg; DE
Gedruckt / Hergestellt in Niederlande.
Sprache: Englisch
106,99 € (DE)
109,99 € (AT)
118,00 CHF (CH)
POD
XXXI, 1111 p. 78 illus.

BC; Hardcover, Softcover / Mathematik/Wahrscheinlichkeitstheorie, Stochastik, Mathematische Statistik; Algorithmen und Datenstrukturen; Verstehen; Informatik; Algorithms; Automata; Categorical semantics; Computational complexity; Constraint satisfaction; Convex optimization; Directed algebraic topology; Dynamic graph algorithms; Foundations of networked computation; Game theory; Logics; Parameterised complexity; Probabilistic systems; Signature schemes; Social networks; Streaming; Theoretical computer science; Theory of programming; Transducer; Universal algebra; Algorithms; Theory of Computation; Computer Communication Networks; Information Storage and Retrieval; Computer and Information Systems Applications; Discrete Mathematics in Computer Science; Theoretische Informatik; Netzwerk-Hardware; Informationsrückgewinnung, Information Retrieval; Data Warehousing; Angewandte Informatik; Mathematik für Informatiker; Diskrete Mathematik; EA

Statistical Randomized Encodings: A Complexity Theoretic View.- Tighter Fourier Transform Lower Bounds.- Quantifying Competitiveness in Paging with Locality of Reference.- Approximation Algorithms for Computing Maximin Share Allocations.- Envy-Free Pricing in Large Markets: Approximating Revenue and Welfare.- Batched Point Location in SINR Diagrams via Algebraic Tools.- On the Randomized Competitive Ratio of Reordering Buffer Management with Non-uniform Costs.- Serving in the Dark Should Be Done Non-uniformly.- Finding the Median (Obliviously) with Bounded Space.- Approximation Algorithms for Min-Sum k-Clustering.- Solving Linear Programming with Constraints Unknown.- Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources.- Limitations of Algebraic Approaches to Graph Isomorphism Testing.- Fully Dynamic Matching in Bipartite Graphs.- Feasible Interpolation for QBF Resolution Calculi.- Simultaneous Approximation of Constraint Satisfaction Problems.- Design of Dynamic Algorithms via Primal-Dual Method.- What Percentage of Programs Halt?.- The Parity of Set Systems Under Random Restrictions with Applications to Exponential Time Problems.- Spotting Trees with Few Leaves.- Constraint Satisfaction Problems over the Integers with Successor.- Hardness Amplification and the Approximate Degree of Constant-Depth Circuits.- Algorithms and Complexity for Turaev-Viro Invariants.- Big Data on the Rise? – Testing Monotonicity of Distributions.- Unit Interval Editing Is Fixed-Parameter Tractable.- Streaming Algorithms for Submodular Function Maximization.- Multilinear Pseudorandom Functions.- Zero-Fixing Extractors for Sub-Logarithmic Entropy.- Interactive Proofs with Approximately Commuting Provers.- Popular Matchings with Two-Sided Preferences and One-Sided Ties.- Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity.- On Convergence and Threshold Properties of Discrete Lotka-Volterra Population Protocols.-Scheduling Bidirectional Traffic on a Path.- On the Problem of Approximating the Eigenvalues of Undirected Graphs in Probabilistic Logspace.- On Planar Boolean CSP.- On Temporal Graph Exploration.- Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation.- A (1+e)-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs.- Lower Bounds for the Graph Homomorphism Problem.- Parameterized Single-Exponential Time Polynomial Space Algorithm for Steiner Tree.- Relative Discrepancy Does not Separate Information and Communication Complexity.- A Galois Connection for Valued Constraint Languages of Infinite Size.- Approximately Counting H Colourings Is #BIS-Hard.- Taylor Polynomial Estimator for Estimating Frequency Moments.- ETR-Completeness for Decision Versions of Multi-player (Symmetric) Nash Equilibria.- Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.- Submatrix Maximum Queries in Monge Matrices Are Equivalent to Predecessor Search.- Optimal Encodings for Range Top-k, Selection, and Min-Max.- 2-Vertex Connectivity in Directed Graphs.- Ground State Connectivity of Local Hamiltonians.- Uniform Kernelization Complexity of Hitting Forbidden Minors.- Counting Homomorphisms to Square-Free Graphs, Modulo 2.- Approximately Counting Locally-Optimal Structures.- Proofs of Proximity for Context-Free Languages and Read-Once Branching Programs (Extended Abstract).- Fast Algorithms for Diameter-Optimally Augmenting Paths.- Hollow Heaps.- Linear-Time List Recovery of High-Rate Expander Codes.- Finding 2-Edge and 2-Vertex Strongly Connected Components in Quadratic Time.- Improved Algorithms for Decremental Single-Source Reachability on Directed Graphs.- Weighted Reordering Buffer Improved via Variants of Knapsack Covering Inequalities.- Local Reductions.- Query Complexity in Expectation.- Near-Linear Query Complexity for Graph Inference.- A QPTAS for the Base of the Number of Crossing-FreeStructures on a Planar Point Set.- Finding a Path in Group-Labeled Graphs with Two Labels Forbidden.- Lower Bounds for Sums of Powers of Low Degree Univariates.- Approximating CSPs Using LP Relaxation.- Comparator Circuits over Finite Bounded Posets.- Algebraic Properties of Valued Constraint Satisfaction Problem.- Towards Understanding the Smoothed Approximation Ratio of the 2-Opt Heuristic.- On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy.- Replacing Mark Bits with Randomness in Fibonacci Heaps.- A PTAS for the Weighted Unit Disk Cover Problem.- Approximating the Expected Values for Combinatorial Optimization Problems Over Stochastic Points.- Deterministic Truncation of Linear Matroids.- Linear Time Parameterized Algorithms for Subset Feedback Vertex Set.- An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains.- Amplification of One-Way Information Complexity via Codes and Noise Sensitivity.- A (2+e)-Approximation Algorithm for the Storage Allocation Problem.- Shortest Reconfiguration Paths in the Solution Space of Boolean Formulas.- Computing the Fréchet Distance Between Polygons with Holes.- An Improved Private Mechanism for Small Databases.- Binary Pattern Tile Set Synthesis Is NP-Hard.- Near-Optimal Upper Bound on Fourier Dimension of Boolean Functions in Terms of Fourier Sparsity.- Condensed Unpredictability.- Sherali-Adams Relaxations for Valued CSPs.- Two-Sided Online Bipartite Matching and Vertex Cover: Beating the Greedy Algorithm.- The Simultaneous Communication of Disjointness with Applications to Data Streams.- An Improved Combinatorial Algorithm for Boolean Matrix Multiplication.