| Description |
1 online resource (xvii, 615 pages) : illustrations |
| Series |
Lecture notes in computer science, 0302-9743 ; 9235 |
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues |
|
Lecture notes in computer science ; 9235. 0302-9743
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
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 |
| Summary |
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) |
| Analysis |
computerwetenschappen |
|
computer sciences |
|
algoritmen |
|
algorithms |
|
computeranalyse |
|
computer analysis |
|
Information and Communication Technology (General) |
|
Informatie- en communicatietechnologie (algemeen) |
| Notes |
International conference proceedings |
|
Includes author index |
|
English |
|
Online resource; title from PDF title page (SpringerLink, viewed August 19, 2015) |
| Subject |
Computer science -- Mathematics -- Congresses
|
|
Computer science -- Mathematics
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Italiano, Giuseppe F., editor.
|
|
Pighizzini, Giovanni, editor.
|
|
Sannella, D. (Donald), 1956- editor.
|
| ISBN |
9783662480540 |
|
3662480549 |
|
