Computer Science - Theory and Applications

Name: Computer Science - Theory and Applications | 13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings
Brand: Springer
Price: 96.29 EUR
Availability: OnlineOnly

13th International Computer Science Symposium in Russia, CSR 2018, Moscow, Russia, June 6-10, 2018, Proceedings

Fedor V. Fomin Vladimir V. Podolskii(Herausgeber*in)

Springer (Verlag)

Erschienen am 24. Mai 2018

XXXII, 335 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-319-90530-3 (ISBN)

96,29 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

Intro
Preface
Organization
Abstract of Invited Talks
Constructive and Non-constructive Combinatorics
Physarum Solves Non-negative Undirected Linear Programs
Limitations of Algebraic Lower Bound Proofs
Complexity of Generation
Lower Bounds for Unrestricted Boolean Circuits: Open Problems
Online Labeling: Algorithms, Lower Bounds and Open Questions
Reading MCSP Through SAT
Recent Developments on the Asymmetric Traveling Salesman Problem
Contents
Complexity of Generation
1 How They Measure Complexity of Generation
2 Hard Generation Problems
2.1 Examples
2.2 Circulation Cones and Polyhedra of Digrahs
2.3 Verifying Boolean Equalities and Inequalities
2.4 Sausage Lemma
2.5 A Sketch of the Proof of Theorem 1 for Digraphs
3 Flash-Light and Supergraph
4 Generating Dual-Bounded Hypergraphs
4.1 Monotone Generation
4.2 Dualization
4.3 Joint Generation BI95,BEGK02,GK95
4.4 Generating (Uniformly) Dual-Bounded Hypergraphs
5 More Examples of Generation Problems
5.1 Monotone Integer Programming BEGK05,BEGKM01,BEGKM02,BEGKM08
5.2 Maximal Frequent and Minimal Infrequent Sets in Data Mining AMSTV96,BGKM3,Elb06
5.3 Minimal Strongly Connected Subgraphs and Dicuts BEGKM04
5.4 Generating Generalized Paths, Cuts, and Spanning Sets in Graphs BEGKM07a,BEGKM07,BEGKM08,RT75
5.5 Spanning Linear Spaces by Linear Subspaces BEGK03,BEGKM08a
5.6 Polymatroid Functions and Systems of Polymatroid Inequalities BEGK03,BEGKM08a,Lov83,McD75
5.7 Uniformly DB Inequalities for Polymatroid Systems BEGK03,BEGKM08a
References
Lower Bounds for Unrestricted Boolean Circuits: Open Problems
1 Computational Model: Boolean Circuits
2 Lower Bounds: Approaches and Open Problems
2.1 Known Lower Bounds and Gate Elimination Method
2.2 Multi-output Functions
2.3 Non-gate-Elimination Lower Bounds
2.4 Symmetric Functions
2.5 Satisfiability Algorithms
2.6 Mass Production
2.7 Logarithmic Depth Circuits
2.8 Linear Circuits and Matrix Rigidity
2.9 Multiplicative Complexity
References
Online Labeling: Algorithms, Lower Bounds and Open Questions
1 The File Maintenance Problem
2 Deterministic Algorithms with Arbitrary Universe
3 The Role of the Universe Size
4 Randomized Online Labeling
References
Maintaining Chordal Graphs Dynamically: Improved Upper and Lower Bounds
1 Introduction
1.1 Previous Work
1.2 Our Results
1.3 Organization of the Paper
2 Decremental Algorithms Using Clique Tree
2.1 Structure with a Worst Case Update Time
2.2 Amortized Analysis
3 Dynamic Maintenance of Perfect Elimination Ordering
3.1 Decremental Algorithm
3.2 Fully Dynamic Maintenance of PEO
4 Lower Bound
5 Conclusions
References
Distributed Symmetry-Breaking Algorithms for Congested Cliques
1 Introduction
1.1 The Congested Clique Model and Problems
1.2 Our Results and Techniques
1.3 Related Work
2 Preliminaries
2.1 Definitions
3 Forest-Decomposition-CC
4 A General Solution with O(a) Time in Congested Clique
5 O(a2)-Coloring in O(loga + log* n) Time
6 O(a2+) -Coloring in O(log* n) Time
7 O(a1+)-Coloring in O(log2 a) Time, O(a)-Coloring in O(a) Time and MIS in O(a) Time
References
The Clever Shopper Problem
1 Introduction
2 Hardness Results
3 Positive Results
4 Approximations
5 Conclusion
References
A Tight Lower Bound for Steiner Orientation
1 Introduction
2 The Reduction
2.1 Construction
2.2 GRID TILING has a Solution STEINER ORIENTATION has a Solution
2.3 STEINER ORIENTATION has a Solution GRID TILING has a Solution
2.4 Obtaining the f(k)No(k) Lower Bound
References
Can We Create Large k-Cores by Adding Few Edges?
1 Introduction
2 Classical Complexity: Polytime Algorithms and NP-hardness
3 Parameterized Complexity: W[1]-Hardness and FPT Algorithms
3.1 FPT Algorithm Parameterized by tw+ k + b
4 Conclusions and Future Directions
References
Periodicity in Data Streams with Wildcards
1 Introduction
1.1 Our Contributions
1.2 Related Work
1.3 Preliminaries
2 Our Approach
3 Two-Pass Algorithm to Compute Wildcard-Periods
3.1 Computing Small Wildcard-Periods
3.2 Verifying Candidates
3.3 Computing Large Wildcard-Periods
4 Lower Bounds
References
Maximum Colorful Cycles in Vertex-Colored Graphs
1 Introduction
2 Hardness Results for MCCP
3 An Algorithm for MCCP in Threshold Graphs
3.1 Case 1: Cc = Cm + 1
3.2 Case 2: Cc = Cm
3.3 Case 3: Cc = Cm - 1
3.4 Algorithm for Threshold Graphs
4 An Algorithm for Bipartite Chain Graphs
References
Grammar-Based Compression of Unranked Trees
1 Introduction
2 Straight-Line Programs over Algebras
3 Forest Algebras and Forest Straight-Line Programs
4 Cluster Algebras and Top Dags
5 Relative Succinctness
6 Testing Equality Modulo Associativity and Commutativity
6.1 Associative Symbols
6.2 Commutative Symbols
7 Future Work
References
Complement for Two-Way Alternating Automata
1 Introduction
2 Two-Way Alternating Automata, Preliminaries
3 Deterministic Machines with Linear Space
4 Two-Way Alternating Automata, Complemented
5 Concluding Remarks
References
Closure Under Reversal of Languages over Infinite Alphabets
1 Introduction
2 Weak Pebble Automata
3 Proof of Theorem1
4 Removing the Distinguished Separator Symbol $
5 Concluding Remark
References
Structural Parameterizations of Dominating Set Variants
1 Introduction
1.1 Motivation
1.2 Definitions, Our Results and Organization of the Paper
2 Preliminaries and Notations
3 Related Work
4 Dominating Set Variants Parameterized by CVD Size
4.1 Upper Bounds
4.2 Lower Bounds
5 Dominating Set Variants Parameterized by SVD Size
5.1 EDS and IDS Parameterized by SVD Size
5.2 Lower Bounds for IDS and EDS
5.3 Improved Algorithm for EDS-SVD
6 Concluding Remarks
References
Complexity and Inapproximability Results for Parallel Task Scheduling and Strip Packing
1 Introduction
2 Hardness of Scheduling Parallel Tasks
3 Hardness of Strip Packing
References
Operations on Boolean and Alternating Finite Automata
1 Introduction
2 Preliminaries
3 Operations on Boolean and Alternating Automata
4 Conclusions
References
Conflict Free Version of Covering Problems on Graphs: Classical and Parameterized
1 Introduction
2 Conflict Free Version of Properties with Forbidden Set Characterizations
2.1 Properties with Finite Forbidden Set Characterizations
2.2 Properties that Do Not Admit Finite Forbidden Characterization
2.3 Results on Properties Without Finite Forbidden Characterization
3 Well Studied Special Cases of CF-FINITE -VD
3.1 CONFLICT FREE VERTEX COVER
4 Conclusion
References
Quadratically Tight Relations for Randomized Query Complexity
1 Introduction
2 Preliminaries
3 Expectational Certificate Complexity
3.1 Quadratic Upper Bound on Randomized Query Complexity
3.2 Relation with the Fractional Certificate Complexity
3.3 Relation with the Certificate Complexity
4 Minimum Query Corruption Bound and Partition Bound
4.1 Upper Bound in Terms of the Corruption Bound and Block Sensitivity
4.2 Quadratic Upper Bound in Terms of the Partition Bound
4.3 Quadratic Upper Bound in Terms of the Corruption Bound
5 Open Problems
References
On Vertex Coloring Without Monochromatic Triangles
1 Introduction
1.1 Related Work
1.2 Our Contribution
1.3 Structure of the Paper
2 Problems
3 Bounds on the Triangle-Free Chromatic Number
3.1 Gadgets
4 Tractable Classes of Graphs
4.1 Graphs with Bounded Chromatic Number
4.2 FPT Results
5 Hardness Results
6 Conclusions and Future Work
References
Recognizing Read-Once Functions from Depth-Three Formulas
1 Introduction
2 Preliminaries
3 Proof of Theorem2
4 Proof of Theorem3
A Proof of Lemma3
B Proof of Lemma4
C Proof of Lemma5
References
MAX-CUT ABOVE SPANNING TREE is Fixed-Parameter Tractable
1 Introduction
2 Preliminaries and Structural Results
3 FPT Algorithm for Max-Cut Above Spanning Tree
4 Polynomial Kernel for Max-Cut-AST
References
Slopes of 3-Dimensional Subshifts of Finite Type
1 Definitions and Properties
1.1 Subshifts and Tilesets
1.2 Periodicity and Aperiodicity
1.3 Arithmetical Hierarchy
2 Proof of Theorem 1
2.1 Every Slope theta of Is Accepted by M
2.2 Accepting Inputs of M Are Slopes of XM
3 Open Problems
References
Facility Location on Planar Graphs with Unreliable Links
1 Introduction
2 An FPT Algorithm for R=1 Under LRO Model
2.1 Dynamic Programming Formulation for Bounded Treewidth
2.2 Recursive Formulation at the Nodes of H
3 A PTAS for MAX-EXP-COVER-1 on planar graphs
References
On the Decision Trees with Symmetries
1 Introduction
2 Preliminaries
3 Polynomial Upper Bounds on SDT
4 Symmetries in a Plain Decision Tree
5 Complexity of PHPnn+1
5.1 Game Interpretation
5.2 Construction of Non-isomorphic Winning Sets
5.3 Naive Invariant
5.4 More Complicated Invariant
5.5 An Upper Bound for the Size of SDT for PHPnn+1
References
On Emptiness and Membership Problems for Set Automata
1 Introduction
2 The Definitions
3 Computational Complexity of the Emptiness Problem
3.1 Successful Automata Runs on a Protocol
3.2 Proof of Lemma 5
4 The Membership Problem for SA
References
On Strong NP-Completeness of Rational Problems
1 Introduction
2 Background
3 Prime Suspects
4 In the Pursuit of Satisfaction
5 Being Rational Makes You Stronger
6 Approximability
7 Conclusions
References
A New Algorithm for Finding Closest Pair of Vectors (Extended Abstract)
1 Introduction
1.1 Our Approach
1.2 Our Results
1.3 Related Work
1.4 Full Version of the Paper
References
Author Index

Systemvoraussetzungen

Als PDF speichern Als Link merken