Mathematical Foundations of Computer Science 2015 [[electronic resource] ] : 40th International Symposium, MFCS 2015, Milan, Italy, August 24-28, 2015, Proceedings, Part II / / edited by Giuseppe F. Italiano, Giovanni Pighizzini, Donald T. Sannella

• Pubblicazione: Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2015
• Edizione: 1st ed. 2015.
• Descrizione fisica: 1 online resource (XVII, 615 p. 58 illus.)
• Disciplina: 004.0151
• Soggetto topico: Algorithms; Computer science—Mathematics; Discrete mathematics; Numerical analysis; Artificial intelligence—Data processing; Machine theory; Discrete Mathematics in Computer Science; Numerical Analysis; Data Science; Formal Languages and Automata Theory; Mathematical Applications in Computer Science
• Persona (resp. second.): ItalianoGiuseppe F; PighizziniGiovanni; SannellaDonald T
• Note generali: Bibliographic Level Mode of Issuance: Monograph
• Nota di bibliografia: Includes bibliographical references and index.
• Nota di contenuto: 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.
• Sommario/riassunto: This two volume set LNCS 9234 and 9235 constitutes the refereed conference proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science, MFCS 2015, held in Milan, Italy, in August 2015. The 82 revised full papers presented together with 5 invited talks were carefully selected from 201 submissions. The papers feature high-quality research in all branches of theoretical computer science. They have been organized in the following topical main sections: logic, semantics, automata, and theory of programming (volume 1) and algorithms, complexity, and games (volume 2).
• Titolo autorizzato: Mathematical Foundations of Computer Science 2015
• ISBN: 3-662-48054-9
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 996200358103316
• Lo trovi qui: Univ. di Salerno
• Serie: Theoretical Computer Science and General Issues, . 2512-2029 ; ; 9235