| Description |
1 online resource (444 pages) |
| Series |
Lecture Notes in Computer Science ; 12159 |
|
LNCS sublibrary, SL 1,Theoretical Computer Science and General Issues |
|
Lecture notes in computer science ; 12159.
|
|
LNCS sublibrary. SL 1, Theoretical computer science and general issues.
|
| Contents |
Intro -- Preface -- Organization -- Contents -- Quantum Hashing and Fingerprinting for Quantum Cryptography and Computations -- 1 Introduction -- 2 Preliminaries -- 3 Quantum Fingerprinting -- 3.1 Binary Quantum Fingerprinting Function -- 3.2 q-ary Quantum Fingerprinting -- 3.3 Quantum Fingerprinting for Computations -- 4 Quantum Hashing -- 4.1 One-way -Resistance -- 4.2 Collision -Resistance -- 4.3 Balanced Quantum (,)-Resistance -- 4.4 Quantum (,)-Hash Functions Construction Via Small-Biased Sets -- 5 Quantum Hashing for Finite Abelian Groups -- 6 Pre-image Resistance of Quantum Hashing |
|
3.1 Derived Relations -- 3.2 Network Positions -- 4 Centrality -- 4.1 Neighborhood Inclusion -- 4.2 Positional Dominance -- 4.3 Homogeneity -- 4.4 Application -- 5 Computational Challenges -- 5.1 Transformations -- 5.2 Dominance -- 5.3 Rankings -- 6 Conclusions -- References -- Second-Order Finite Automata -- 1 Introduction -- 2 Preliminaries -- 2.1 Basics -- 2.2 Ordered Decision Diagrams -- 3 Second-Order Finite Automata -- 4 Transductions -- 5 Canonization of ODDs Using Transductions -- 6 Applications -- 7 Conclusion -- References -- Isomorphic Distances Among Elections -- 1 Introduction |
|
1.1 Distances, Election Isomorphism, and Motivation -- 1.2 Organization -- 2 Preliminaries -- 3 Distances Among Elections -- 3.1 Election Isomorphism Problem -- 3.2 Isomorphic Distances -- 3.3 Positionwise and Pairwise Distances -- 4 Research Directions -- 4.1 New Distances -- 4.2 Effective Algorithms -- 4.3 Properties of the Distances -- 4.4 Evaluating Distances in Practice -- 5 Summary -- References -- Tandem Duplications, Segmental Duplications and Deletions, and Their Applications -- 1 Introduction -- 1.1 Tandem Duplications -- 1.2 Copy Number Profiles -- 2 Preliminaries |
|
2.1 Strings and Tandem Duplications -- 2.2 Copy Number Profiles, Segmental Duplications and Deletions -- 3 Results on Tandem Duplications -- 3.1 Exemplar-TD Is NP-hard -- 3.2 Exemplar-TD Is FPT -- 4 Results on Copy Number Profiles -- 4.1 Hardness of Approximation for MCNG -- 4.2 W[1]-Hardness for MCNG -- 4.3 The Copy Number Profile Conforming Problem -- 5 Concluding Remarks and Open Problems -- References -- Faster 2-Disjoint-Shortest-Paths Algorithm -- 1 Introduction -- 2 Definitions and the DP Formululation -- 3 Reducing the Running Time to O(V7) -- 4 Reducing Running Time to O(V6) |
| Summary |
This book constitutes the proceedings of the 15th International Computer Science Symposium in Russia, CSR 2020, held in Yekaterinburg, Russia, in June 2020. The 25 full papers and 6 invited papers were carefully reviewed and selected from 49 submissions. The papers cover a broad range of topics, such as: algorithms and data structures; computational complexity, including hardness of approximation and parameterized complexity; randomness in computing, approximation algorithms, fixed-parameter algorithms; combinatorial optimization, constraint satisfaction, operations research; computational geometry; string algorithms; formal languages and automata, including applications to computational linguistics; codes and cryptography; combinatorics in computer science; computational biology; applications of logic to computer science, proof complexity; database theory; distributed computing; fundamentals of machine learning, including learning theory, grammatical inference and neural computing; computational social choice; quantum computing and quantum cryptography; theoretical aspects of big data. The conference was cancelled as a live conference due to the corona pandemic. -- Provided by publisher |
| Notes |
International conference proceedings |
| Bibliography |
References-Parameterized Analysis of Art Gallery and Terrain Guarding-1 Background on Parameterized Analysis-2 The Art Gallery Problem-2.1 Known Algorithmic Works-2.2 Giannopoulos's Parameterization and Our Contribution-3 The Terrain Guarding Problem-3.1 Known Algorithmic Works-3.2 Subexponential-Time Parameterized Algorithm for Terrain Guarding and FPT Algorithm for Orthogonal Terrain Guarding-References-Central Positions in Social Networks-1 Introduction-2 Network Data-2.1 Variables-2.2 Network Variables-2.3 Graph Representations-3 Positions |
| Notes |
5 Experimental Evaluation |
|
Includes author index |
|
Print version record |
| Subject |
Computer science -- Congresses
|
|
Computer algorithms -- Congresses
|
|
Discrete mathematics.
|
|
Algorithms & data structures.
|
|
Mathematical theory of computation.
|
|
Computer science.
|
|
Computers -- Data Processing.
|
|
Computers -- Information Theory.
|
|
Computers -- Computer Science.
|
|
Computer algorithms
|
|
Computer science
|
| Genre/Form |
proceedings (reports)
|
|
Conference papers and proceedings
|
|
Conference papers and proceedings.
|
|
Actes de congrès.
|
| Form |
Electronic book
|
| Author |
Fernau, Henning, 1965-
|
| ISBN |
9783030500269 |
|
3030500268 |
|
