Kooperativer Bibliotheksverbund

UID:

Format: XXXIV, 1090 p. 74 illus. , online resource.

ISBN: 9783662439487

Series Statement: Lecture Notes in Computer Science, 8572

Content: This two-volume set of LNCS 8572 and LNCS 8573 constitutes the refereed proceedings of the 41st International Colloquium on Automata, Languages and Programming, ICALP 2014, held in Copenhagen, Denmark, in July 2014. The total of 136 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 484 submissions. The papers are organized in three tracks focussing on Algorithms, Complexity, and Games, Logic, Semantics, Automata, and Theory of Programming, Foundations of Networked Computation.

Note: 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.

In: Springer eBooks

Additional Edition: Printed edition: ISBN 9783662439470

Language: English

Keywords: Konferenzschrift

DOI: 10.1007/978-3-662-43948-7

URL: http://dx.doi.org/10.1007/978-3-662-43948-7

URL: Volltext  (lizenzpflichtig)

URL: Volltext  (lizenzpflichtig)

URL: Cover

URL: Inhaltstext

UID:

Format: XXX, 624 p. 49 illus. , online resource.

ISBN: 9783662439517

Series Statement: Lecture Notes in Computer Science, 8573

Content: This two-volume set of LNCS 8572 and LNCS 8573 constitutes the refereed proceedings of the 41st International Colloquium on Automata, Languages and Programming, ICALP 2014, held in Copenhagen, Denmark, in July 2014. The total of 136 revised full papers presented together with 4 invited talks were carefully reviewed and selected from 484 submissions. The papers are organized in three tracks focussing on Algorithms, Complexity, and Games, Logic, Semantics, Automata, and Theory of Programming, Foundations of Networked Computation.

Note: Track B: Logic, Semantics, Automata, and Theory of Programming -- Symmetric Groups and Quotient Complexity of Boolean Operations -- Handling Infinitely Branching WSTS -- Transducers with Origin Information -- Weak MSO+U with Path Quantifiers over Infinite Trees -- On the Decidability of MSO+U on Infinite Trees -- A Coalgebraic Foundation for Coinductive Union Types -- Turing Degrees of Limit Sets of Cellular Automata -- On the Complexity of Temporal-Logic Path Checking -- Parameterised Linearisability -- Games with a Weak Adversary -- The Complexity of Ergodic Mean-payoff Games -- Toward a Structure Theory of Regular Infinitary Trace Languages -- Unary Pushdown Automata and Straight-Line Programs -- Robustness against Power is PSpace-complete -- A Nivat Theorem for Weighted Timed Automata and Weighted Relative Distance Logic -- Computability in Anonymous Networks: Revocable vs. Irrecovable Outputs -- Coalgebraic Weak Bisimulation from Recursive Equations over Monads -- Piecewise Boolean Algebras and Their Domains -- Between Linearizability and Quiescent Consistency: Quantitative Quiescent Consistency -- Bisimulation Equivalence of First-Order Grammars -- Context Unification is in PSPACE -- Monodic Fragments of Probabilistic First-Order Logic -- Stability and Complexity of Minimising Probabilistic Automata -- Kleene Algebra with Equations -- All–Instances Termination of Chase is Undecidable -- Non-uniform Polytime Computation in the Infinitary Affine Lambda-Calculus -- On the Positivity Problem for Simple Linear Recurrence Sequences -- Ultimate Positivity is Decidable for Simple Linear Recurrence Sequences -- Going Higher in the First-Order Quantifier Alternation Hierarchy on Words -- Hardness Results for Intersection Non-Emptiness -- Branching Bisimilarity Checking for PRS -- Track C: Foundations of Networked Computing Labeling Schemes for Bounded Degree Graphs -- Bounded-Angle Spanning Tree: Modeling Networks with Angular Constraints -- Distributed Computing on Core-Periphery Networks: Axiom-Based Design 399 -- Fault-Tolerant Rendezvous in Networks -- Data Delivery by Energy-Constrained Mobile Agents on a Line -- The Power of Two Choices in Distributed Voting -- Jamming-Resistant Learning in Wireless Networks -- Facility Location in Evolving Metrics -- Solving the ANTS Problem with Asynchronous Finite State Machines -- Near-Optimal Distributed Approximation of Minimum-Weight Connected Dominating Set -- Randomized Rumor Spreading in Dynamic Graphs -- Online Independent Set Beyond the Worst-Case: Secretaries, Prophets, and Periods -- Optimal Competitiveness for Symmetric Rectilinear Steiner Arborescence and Related Problems -- Orienting Fully Dynamic Graphs with Worst-Case Time Bounds -- Does Adding More Agents Make a Difference? A Case Study of Cover Time for the Rotor-Router -- The Melbourne Shuffle: Improving Oblivious Storage in the Cloud -- Sending Secrets Swiftly: Approximation Algorithms for Generalized Multicast Problems -- Bypassing Erdos’ Girth Conjecture: Hybrid Stretch and Sourcewise Spanners.

In: Springer eBooks

Additional Edition: Printed edition: ISBN 9783662439500

Language: English

Keywords: Konferenzschrift

DOI: 10.1007/978-3-662-43951-7

URL: http://dx.doi.org/10.1007/978-3-662-43951-7

URL: Volltext  (lizenzpflichtig)

URL: Volltext  (lizenzpflichtig)

URL: Cover

URL: Inhaltstext

UID:

Format: XII, 420 p. , online resource.

ISBN: 9783642255106

Series Statement: Lecture Notes in Computer Science, 7090

Content: This book constitutes the refereed proceedings of the 7th International Workshop on Internet and Network Economics, WINE 2011, held in Singapore, in December 2011. The 31 revised full papers and 5 revised short papers presented together with the abstracts of 3 papers about work in progress were carefully reviewed and selected from 100 submissions. The papers are orginzed in topical sections on algorithmic game theory, algorithmic mechanism design, computational advertising, computational social choice, convergence and learning in games, economics aspects of security and privacy, information and attention economics, network games and social networks.

In: Springer eBooks

Additional Edition: Printed edition: ISBN 9783642255090

Language: English

DOI: 10.1007/978-3-642-25510-6

URL: http://dx.doi.org/10.1007/978-3-642-25510-6

UID:

Format: VIII, 359 p. 25 illus. , online resource.

ISBN: 9783642161704

Series Statement: Lecture Notes in Computer Science, 6386

Note: When the Players Are Not Expectation Maximizers -- How Do You Like Your Equilibrium Selection Problems? Hard, or Very Hard? -- A Simplex-Like Algorithm for Fisher Markets -- Nash Equilibria in Fisher Market -- Partition Equilibrium Always Exists in Resource Selection Games -- Mixing Time and Stationary Expected Social Welfare of Logit Dynamics -- Pareto Efficiency and Approximate Pareto Efficiency in Routing and Load Balancing Games -- On Nash-Equilibria of Approximation-Stable Games -- Improved Lower Bounds on the Price of Stability of Undirected Network Design Games -- On the Rate of Convergence of Fictitious Play -- On Learning Algorithms for Nash Equilibria -- On the Structure of Weakly Acyclic Games -- A Direct Reduction from k-Player to 2-Player Approximate Nash Equilibrium -- Responsive Lotteries -- On the Existence of Optimal Taxes for Network Congestion Games with Heterogeneous Users -- Computing Stable Outcomes in Hedonic Games -- A Perfect Price Discrimination Market Model with Production, and a (Rational) Convex Program for It -- The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements -- Complexity of Safe Strategic Voting -- Bottleneck Congestion Games with Logarithmic Price of Anarchy -- Single-Parameter Combinatorial Auctions with Partially Public Valuations -- On the Efficiency of Markets with Two-Sided Proportional Allocation Mechanisms -- Braess’s Paradox for Flows over Time -- The Price of Anarchy in Network Creation Games Is (Mostly) Constant -- Truthful Fair Division -- No Regret Learning in Oligopolies: Cournot vs. Bertrand -- On the Complexity of Pareto-optimal Nash and Strong Equilibria -- 2-Player Nash and Nonsymmetric Bargaining Games: Algorithms and Structural Properties -- On the Inefficiency of Equilibria in Linear Bottleneck Congestion Games -- Minimal Subsidies in Expense Sharing Games.

In: Springer eBooks

Additional Edition: Printed edition: ISBN 9783642161698

Language: English

DOI: 10.1007/978-3-642-16170-4

URL: http://dx.doi.org/10.1007/978-3-642-16170-4

UID:

Format: 1 online resource (359 pages)

ISBN: 9783642161698

Series Statement: ACM Other conferences

Note: Title from The ACM Digital Library

Language: English

Keywords: Konferenzschrift

DOI: 10.5555/1929237

URL: lizenzpflichtig

URL: Inhaltstext