Mathematical Foundations of Computer Science 2015

Name: Mathematical Foundations of Computer Science 2015 | 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II

Giuseppe F. Italiano Giovanni Pighizzini Donald T. Sannella(Editor)

Springer (Publisher)

Published on 10. August 2015

XVII, 615 pages

E-Book

PDF with digital watermarking

System requirements

978-3-662-48054-0 (ISBN)

€53.49incl. 7% vat

System requirements

for PDF with digital watermarking

E-Book Single Licence

Available for download

Description

More details

Other editions

Content

Intro
Preface
Conference Organization
Contents - Part II
Contents - Part I
Near-Optimal Asymmetric Binary Matrix Partitions
1 Introduction
2 Preliminaries
3 The Uniform Case
4 Asymmetric Binary Matrix Partition as Welfare Maximization
References
Dual VP Classes
1 Introduction
1.1 ACC1 and TC1
1.2 Algebraic Degree
1.3 Duality
2 Preliminaries, and Definitions of -classes
3 Subclasses of ACC1
3.1 Comparing P and VP.
4 Threshold Circuits and Small Degree
4.1 Degree Reduction
5 Conclusions, Discussion, and Open Problems
References
On Tinhofer's Linear Programming Approach to Isomorphism Testing
1 Introduction
2 Amenable Graphs
3 Amenable Graphs Are Compact
4 A Color-Refinement Based Hierarchy of Graphs
References
On the Complexity of Noncommutative Polynomial Factorization
1 Introduction
2 Variable-Disjoint Factorization Problem
2.1 Uniqueness of Variable-Disjoint Factorization
2.2 Equivalence with PIT
2.3 Black-Box Variable-Disjoint Factorization Algorithm
3 Factorization of Multilinear and Homogeneous Polynomials
4 A Polynomial Decomposition Problem
5 Concluding Remarks and Open Problems
References
An Algebraic Proof of the Real Number PCP Theorem
1 Introduction
1.1 Problems with the Classical Proof and Outline
2 Basic Notions
2.1 Testing Trigonometric Polynomials
3 The Correctness Test
4 Segmented Almost Transparent Proofs for NPR
References
On the Complexity of Hub Labeling (Extended Abstract)
1 Introduction
2 Preliminaries
2.1 HL Approximation Algorithm
2.2 Greedy HHL Algorithms
3 HHL and Highway Dimension
4 Upper Bounds
5 Lower Bounds
6 NP-Hardness Proofs
6.1 Undirected Graphs
6.2 Directed Graphs
7 HL vs HHL
8 Concluding Remarks
References
On the Complexity of Speed Scaling
1 Introduction
2 Model and Notation
3 Hardness Results
3.1 Hardness of B-IDUA
4 Polynomial Time Algorithms
4.1 An Algorithm for FE-IDUU
4.2 An Algorithm for FE-ICUU
4.3 An Algorithm for FE-FCWA
5 Equivalence Reductions
5.1 Reducing B-ICUU to FE-ICUU
5.2 Reducing the Discrete to the Continuous Setting
5.3 Reducing from Budget to Flow Plus Energy for Fractional Flow
References
Almost All Functions Require Exponential Energy
1 Introduction
1.1 Our Contributions
1.2 Related Work
1.3 Formal Model
2 A Lower Bound on the Number of Functions Computable by a Circuit
2.1 Homogeneous Supply Voltages
2.2 Heterogeneous Supply Voltages
3 Almost All Functions Require Exponential Energy
3.1 Adaptation of Shannon's Argument
3.2 Homogeneous Supply Voltages
3.3 Heterogeneous Supply Voltages
4 Relating Energy and the Number of Faulty Gates
References
On Dynamic DFS Tree in Directed Graphs
1 Introduction
1.1 An Efficient Decremental Algorithm for a DFS Tree in a DAG
1.2 Lower Bounds on Dynamic DFS Tree
1.3 Organization of the Paper
2 Preliminaries
3 A Simple and Deterministic Decremental Algorithm
4 An Efficient Randomized Algorithm
4.1 Analysis of the Algorithm
5 Lower Bounds for Dynamic DFS Tree Problem
5.1 Maintaining Ordered DFS Tree Explicitly
5.2 Partial Dynamic Ordered DFS Tree and Static All-Pairs Reachability
6 Conclusion
References
Metric Dimension of Bounded Width Graphs
1 Introduction
2 Basic Definitions and Preliminaries
3 Metric Dimension on Graphs of Bounded Tree-Length and Max-Degree
3.1 Properties of Graphs of Bounded Tree-Length and Max-Degree
3.2 The Algorithm
4 Metric Dimension on Graphs of Bounded Modular-Width
5 Conclusions
References
Equality, Revisited
1 Introduction
2 Our Results
3 The New Lower Bound Technique
4 Extensions
4.1 QR Protocols
4.2 The ``One Out of Two'' Problem
5 Lower Bounds
5.1 Bounds for NE
5.2 Bounds for EQ
6 Protocols
6.1 Tightness for NE and RRR Protocols
6.2 Tightness for QRQ and RRQ Protocols
7 Untrusted Quantum State Transfer
7.1 A Protocol
7.2 A Lower Bound
8 Discussion
References
Bounding the Clique-Width of H-free Chordal Graphs
1 Introduction
2 Preliminaries
3 New Classes of Bounded and Unbounded Clique-Width
4 Concluding Remarks
References
New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory
1 Introduction
1.1 Our Results
1.2 Related Work
2 Definitions and Results
2.1 Notations and Definitions
2.2 Lower Bound Techniques
3 An Upper Bound
4 Lower Bounds
References
QMA with Subset State Witnesses
1 Introduction
2 Preliminaries
2.1 Definitions
2.2 Complexity Classes and Complete Problems
3 Subset State Approximations
4 Alternative Characterisations of QMA
5 A QMA-Complete Problem Based on Subset States
6 On the Perfectly Complete Version of SQMA
7 Conclusions
References
Phase Transition for Local Search on Planted SAT
1 Preliminaries
2 Success of Local Search
3 Failure of Local Search
References
Optimal Bounds for Estimating Entropy with PMF Queries
1 Introduction
1.1 Our Results, and Comparison with Prior Work
2 Lower Bound for Estimating Shannon Entropy
3 Estimating Rényi Entropy
4 Lower Bound for Estimating Support Size
5 Concluding Remarks
References
Mutual Dimension and Random Sequences
1 Introduction
2 Mutual Dimension in Cantor Spaces
3 Mutual Dimension and Coupled Randomness
4 Billingsley Mutual Dimensions
References
Optimal Algorithms and a PTAS for Cost-Aware Scheduling
1 Introduction
2 Minimizing the Makespan on Unrelated Machines
3 Minimizing on a Single Machine
4 A PTAS for Minimizing Total Weighted Completion Time
4.1 Preliminaries and Scheduling in the Weight-Dimension
4.2 Dynamic Programming Algorithm
4.3 Trimming the State Space
5 Open Problems
References
Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases
1 Introduction
1.1 Our Results and Proof Techniques
1.2 Related Work
2 Preliminaries
3 Shrinkage Under Restrictions
3.1 Formula Simplification
3.2 Weight Reduction Under Restrictions
3.3 Upper Bounds on Formula Weights
3.4 Choice of Weight Parameters
4 A Satisfiability Algorithm
5 Average-Case Lower Bounds
6 Formulas over Unate Bases
7 Open Questions
References
Randomized Polynomial Time Protocol for Combinatorial Slepian-Wolf Problem
1 Introduction
2 Preliminaries
3 Auxiliarely Communication Models: Shared and Imperfect Randomness
4 An Effective Protocol for Model 1 (Partially Shared Sources of Perfect Randomness)
4.1 Parameters of the Construction
4.2 The Scheme of the Protocol
4.3 Communication Complexity of the Protocol
5 An Effective Protocol for Model 2
6 The Model with Private Sources of Perfect Randomness
7 Conclusion
References
Network Creation Games: Think Global -- Act Local
1 Introduction
2 Computational Hardness and Game Dynamics
3 Local versus Global Moves
4 The Quality of k-Local Equilibria
4.1 Conformity of k-Local and Nash Equilibria
4.2 The Price of Anarchy for Tree Networks
4.3 The Price of Anarchy for Non-tree Networks
5 Conclusion and Open Problems
References
Oblivious Transfer from Weakly Random Self-Reducible Public-Key Cryptosystem
1 Introduction
2 Previous Work
3 Background Material
4 Random Self-Reducible Encryption Scheme
5 2()1-OT from a RSR Public-Key Cryptosystem
6 Weakly Random Self-Reducible Encryption
6.1 Instantiation of wRSR Public-Key Cryptosystems
6.2 Approximate Integer GCD
6.3 Learning with Errors (LWE)
7 Conclusion and Open Problem
References
Efficient Computations over Encrypted Data Blocks
1 Introduction
2 Definitions and Background
2.1 Efficient and Secure 2-Party Evaluation of Equality-Based Formulae
2.2 Protocols and Cryptographic Primitives Used in Our Solutions
3 Real-or-Random Conditional Transfer Protocols
3.1 An srCTeval Protocol for the Equality Predicate
3.2 An srCTeval Protocol for the AND-of-Equality Predicate
3.3 An srCTeval Protocol for the OR-of-Equality Predicate
4 Secure Evaluation of Equality-Based Monotone Formulae
5 Conclusions
References
Polynomial Kernels for Weighted Problems
1 Introduction
2 Preliminaries
3 Settling Open Problems via the Frank-Tardos Theorem
3.1 Frank and Tardos' Theorem
3.2 Polynomial Kernelization for Knapsack
4 Small Kernels for Weighted Parameterized Problems
4.1 Hitting Set and Set Packing
4.2 Max Cut
4.3 Polynomial Kernelization for Bin Packing with Additive Error
5 Kernel Bounds for Knapsack Problems
5.1 Exponential Kernel for Knapsack with Few Item Sizes
5.2 Polynomial Kernel for Subset Sum with Few Item Sizes
5.3 A Kernelization Lower Bound for Subset Sum
6 Integer Polynomial Programming with Bounded Range
7 Conclusion
References
A Shortcut to (Sun)Flowers: Kernels in Logarithmic Space or Linear Time
1 Introduction
2 Preliminaries
3 Sunflowers and Flowers
4 Logspace Kernel for Hitting Set
5 Logspace Kernel for Set Packing
6 Linear-Time Kernels for Hitting Set and Set Packing
7 Concluding Remarks
References
Metastability of Asymptotically Well-Behaved Potential Games
1 Introduction
2 Preliminary Definitions
3 Asymptotic Metastability and Partitioned Games
4 Asymptotically Well-Behaved Potential Games
5 Conclusions and Open Problems
References
The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials
1 Introduction
2 Proving Theorem 1: High-Level Outline
3 Proving Theorem 1: Details
3.1 Choice of Basis: Step 1 of the Proof
3.2 Choice of Shifts: Step 2 of the Proof
3.3 Bounding the Rank of M: Step 3 of the Proof
3.4 Putting it Together
4 Lower Bound on the Size of Depth Four Formulas
References
Parameterized Algorithms for Parity Games
1 Introduction
2 Definitions and Preliminaries
2.1 Parity Games, Dominions and Attractors
2.2 Attractor-Based Algorithms
3 Strong Dominion Hitters
3.1 Direct Applications
3.2 More Involved Case
4 Modular Width and Graphs with k Modules
4.1 Exponential FPT Algorithm
4.2 Sub-exponential FPT Algorithm
5 Hardness Results
5.1 Finding Dominions
5.2 Rabin Games
References
Algorithmic Applications of Tree-Cut Width
1 Introduction
2 Preliminaries
2.1 Basic Notation
2.2 Parameterized Complexity
2.3 Integer Linear Programming
2.4 Tree-Cut Width
2.5 Relations to Other Width Parameters
3 Nice Tree-Cut Decompositions
4 FPT Algorithms
4.1 Capacitated Vertex Cover
4.2 Imbalance
4.3 Capacitated Dominating Set
5 Lower Bounds
6 Concluding Notes
References
Log-Concavity and Lower Bounds for Arithmetic Circuits
1 Introduction
2 The Kurtz Log-Concavity Condition
3 A Stronger Log-Concavity Condition
4 Applications to Complexity Theory
5 Discussion
References
Easy Multiple-Precision Divisors and Word-RAM Constants
1 Introduction
2 Arithmetic Operations on Easy Numbers
2.1 Word Covers
2.2 Multiplication and Division by Easy Numbers
3 Computing Tables of Polynomials
References
Visibly Counter Languages and the Structure of NC1
1 Introduction
2 Preliminaries
3 Height Computation for Visibly Counter Languages
4 The Regular Part of Visibly Counter Languages
5 Results on Logic
6 Results on Circuits
7 Discussion
References
The Price of Connectivity for Cycle Transversals
1 Introduction
2 Preliminaries and Some Basic Results
3 Transversals of Families of Odd Cycles
4 Cycle Families with 4-Cycles but No 3-Cycles
5 Cycle Families with 5-Cycles but No 3- or 4-Cycles
6 Conclusions
References
Upper and Lower Bounds on Long Dual Paths in Line Arrangements
1 Introduction
1.1 State of the Art
1.2 Results and Outline
1.3 Preliminaries
2 Long Paths in Pseudoline Arrangements
3 Open Problem
References
A Numbers-on-Foreheads Game
1 Introduction
1.1 Related Work
1.2 Notation and Preliminaries
2 Relation Between Gambling Games and Total Variation Distance
3 Upper Bound
4 Lower Bound
5 Conclusion
References
Faster Lightweight Lempel-Ziv Parsing
1 Introduction
2 Short Factors
3 Medium Factors
3.1 Main Tools
3.2 Indexing Data Structure
3.3 Algorithm for Medium Factors
4 Long Factors
4.1 Main Tools
4.2 Algorithm for Long Factors
References
Parallel Identity Testing for Skew Circuits with Big Powers and Applications
1 Introduction
2 Background from Complexity Theory
3 Polynomials and Circuits
4 PIT for Powerful Skew Circuits
5 Multi-dimensional Straight-Line Programs
6 Circuits Over Wreath Products
6.1 Compressed Word Problems
6.2 Wreath Products
6.3 CWP(Z Z) and Identity Testing for Powerful Skew Circuits
References
On Probabilistic Space-Bounded Machines with Multiple Access to Random Tape
1 Introduction
2 Preliminaries
3 Space-Bounded Machines with Multiple Passes Over the Random Tape
3.1 Derandomization of Probabilistic Time
3.2 Simulating Multiple Passes with Single Pass
3.3 Deterministic Simulation of Multi-pass Machines with Linear Advice
4 Conclusions
References
Densest Subgraph in Dynamic Graph Streams
1 Introduction
1.1 Our Results and Previous Work
1.2 Our Approach and Paper Outline
2 Subsampling Approximately Preserves Maximum Density
3 Implementing in the Dynamic Data Stream Model
3.1 Reformulating the Sampling Procedure
3.2 The Dynamic Graph Stream Algorithm
4 Conclusion
References
The Offline Carpool Problem Revisited
1 Introduction
2 Related Work
3 Our Contribution
4 Generalizing the Online Algorithm
5 A Fair Schedule
6 A Non-bursty Schedule
7 The Final Algorithm
8 Conclusion
References
On Sampling Simple Paths in Planar Graphs According to Their Lengths
1 Introduction
1.1 Our Results
2 Preliminaries
3 A Markov Chain for Planar Graphs
4 Analysis of Mpaths
5 A Rapidly Mixing Chain for Vertical-Monotone Paths
5.1 Mixing Time of Mmon
6 Conclusion
References
Degree-Constrained Subgraph Reconfiguration is in P
1 Introduction
2 Notation
3 ab-Constrained Subgraph Reconfiguration
3.1 Obstructions
3.2 Internal Alternating Trail Reconfiguration
3.3 External Alternating Trail Reconfiguration
3.4 Reconfiguring ab-constrained Subgraphs
References
Generalized Pseudoforest Deletion: Algorithms and Uniform Kernel
1 Introduction
2 Preliminaries
2.1 Preliminary Results
3 A clk nO(1) Algorithm for l-pseudoforest Deletion
4 A ck nO(1) Algorithm for Pseudoforest Deletion
5 Kernels
5.1 Degree Reduction
5.2 Kernels Through Protrusions
5.3 An Explicit Kernel for Pseudoforest Deletion
6 Conclusions
References
Efficient Equilibria in Polymatrix Coordination Games
1 Introduction
2 Preliminaries
3 Existence
4 Inefficiency
5 Complexity
6 Coordination Mechanisms
References
Finding Consensus Strings with Small Length Difference Between Input and Solution Strings
1 Introduction
2 Alphabet Reduction and Exact Exponential Algorithm
3 Closest Substring
4 Consensus Patterns
4.1 The Parameter (- m)
References
Active Linking Attacks
1 Protocol Model and Security Definition
1.1 Protocol Execution
2 Insecure Protocols: Tracking Strategies
3 Secure Protocols: Proof Techniques and a Characterization
3.1 Secure Flat Protocols
3.2 Security Proofs for General Protocols
4 Conclusion
References
On the Complexity of Master Problems
1 Introduction
2 The Master Satisfiability Problem with Scenarios
3 The Master Tour Problem with Scenarios
4 The Master Tree Problem with Scenarios
5 Conclusion
References
Efficient Algorithm for Computing All Low s-t Edge Connectivities in Directed Graphs
1 Introduction
2 Preliminaries
3 Flow-Equivalent Tree for Directed Graph
4 Computing Low Edge Connectivities
4.1 Block Refinement
4.2 Computing the Current Flow with Seed Replacement
4.3 Complexity of the Construction
References
Maximum Minimal Vertex Cover Parameterized by Vertex Cover
1 Introduction
1.1 Related Work
1.2 Our Contribution
2 Upper and Lower Bounds
3 A Parameterized Approximation Algorithm
3.1 The Bounded Search Tree Technique
3.2 ProcedureA: The Proof of Lemma 3
3.3 ProcedureB: The Proof of Lemma 4
References
Fast Dynamic Weight Matchings in Convex Bipartite Graphs
1 Introduction
2 Terminologies and Definitions
3 Optimal Matched Set, Replaceable Set, and Tight Subgraph
4 Extended Binary Computation Tree
5 Dynamic Updates
5.1 Inserting x in a Leaf Node
5.2 Inserting x in an Internal Node
6 Fast Dynamic Queries
References
Author Index

System requirements

Save as PDF Copy link into clipboard

Schweitzer Fachinformationen

Mathematical Foundations of Computer Science 2015

Description

More details

Other editions

Additional editions

Content

System requirements