Computer Science - Theory and Applications
6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings
Published on 12. June 2011
XI, 471 pages
978-3-642-20712-9 (ISBN)
Description
This book constitutes the proceedings of the 6th International Computer Science Symposium in Russia, CSR 2011, held in St. Petersburg, Russia, in June 2011. The 29 papers presented were carefully reviewed and selected from 76 submissions. The scope of topics of the symposium was quite broad and covered basically all areas of the foundations of theoretical computer science.
More details
Other editions
Additional editions
Alexander Kulikov | Nikolay Vereshchagin
Computer Science - Theory and Applications
6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings
Book
06/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Organization
- Table of Contents
- The Equivalence of Sampling and Searching
- Introduction
- Background
- Our Results
- Proof Overview
- Preliminaries
- Sampling and Search Problems
- Algorithmic Information Theory
- Information Theory
- Main Result
- Implication for Quantum Computing
- Extensions and Open Problems
- Equivalence of Sampling and Decision Problems?
- Was Kolmogorov Complexity Necessary?
- From Search Problems to Sampling Problems
- Making the Search Problem Checkable
- References
- Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity
- Introduction
- Notation and Previous Black-Box Models
- Notation
- Unrestricted and Unbiased Black-Box Model
- The Ranking-Based Black-Box Model
- Ranking-Based Black-Box Complexity of OneMax
- The Different Black-Box Complexities of BinaryValue
- Ranking-Based Black-Box Complexity of LeadingOnes
- Conclusions
- References
- Learning Read-Constant Polynomials of Constant Degree Modulo Composites
- Introduction
- Preliminaries
- Polynomials over Finite Rings
- Structural Properties of Polynomials
- Learning with Membership Queries
- Equivalence Relations between Monomials
- Idea of the Learning Algorithm
- Properties of Polynomials Equipped with a Magic Set
- The Learning Algorithm
- Extensions to Higher Degrees
- Future Work
- References
- On the Arithmetic Complexity of Euler Function
- Introduction
- Arithmetic Complexity Classes and Permanent Polynomial
- The Family { E,n(x) }n & 0
- The Family { E,n(x) }n & 0
- Black-Box Derandomization of PIT
- Open Questions
- References
- Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error
- Introduction
- How BMRV-Scheme Works
- Proof of Theorem 5
- Refinement of the Property of -Reduction
- Testing the Property of Strong -Reduction
- Pseudo-random Graphs
- Complexity of Encoding
- Proof of Theorem 6: Effective Encoding
- Conclusion
- References
- Improving the Space-Bounded Version of Muchnik's Conditional Complexity Theorem via "Naive" Derandomization
- Introduction
- Preliminaries
- Kolmogorov Complexity
- Extractors
- Nisan-Wigderson Generators
- Constant-Depth Circuits for Approximate Counting
- Muchnik's Theorem
- Subject Overview
- Proof Overview
- Low-Congesting Graphs
- Space-Bounded Enumerability
- Derandomization
- Proof of the Theorem
- References
- The Complexity of Solving Reachability Games Using Value and Strategy Iteration
- Introduction
- Statement of Problem and Overview of Results
- Overview of Proof Techniques
- Theorems and Proofs
- The Connection between Patience, the Value of Time Bounded Games, and the Complexity of Value Iteration
- The Value of Time Bounded Generalized Purgatory and the Complexity of Value Iteration
- Strategy Iteration
- References
- Faster Polynomial Multiplication via Discrete Fourier Transforms
- Introduction
- Model of Computation
- Fast Polynomial Multiplication and Lower Bounds
- Our Results
- Organization of the Paper
- Basic Definitions
- An Upper Bound on the Complexity of DFT
- Unified Approach for Fast Polynomial Multiplication
- Extension Degree and Order Sequence
- Generalized Algorithm for Polynomial Multiplication
- Complexity Analysis
- Conclusion
- References
- Kolmogorov Complexity as a Language
- Introduction
- Foundations of Probability Theory
- Random Sequences
- Sampling Random Strings
- Counting Arguments and Existence Proofs
- A Simple Example
- One-Tape Turing Machines
- Forbidden Patterns and Everywhere Complex Sequences
- Gilbert-Varshamov Bound and Its Generalization
- Complexity and Combinatorial Statements
- Inequalities for Kolmogorov Complexity and Their Combinatorial Meaning
- Common Information and Graph Minors
- Almost Uniform Sets
- Shannon Information Theory
- Shannon Coding Theorem
- Complexity, Entropy and Group Size
- Muchnik's Theorem
- Romashchenko's Theorem
- Computability (Recursion) Theory
- Simple Sets
- Lower Semicomputable Random Reals
- Other Examples
- Constructive Proof of Lovasz Local Lemma
- Berry, Gödel, Chaitin, Raz
- 13th Hilbert Problem
- Secret Sharing
- Quasi-cryptography
- References
- Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs
- Introduction
- Branching Programs and the Richness Condition
- Almost k-Wise Independent Sets Are Rich
- Modifications of Partition Classes
- Almost k-Wise Independence
- Frequent Cardinalities
- Taylor's Theorem
- Conclusion
- References
- The Complexity of Inversion of Explicit Goldreich's Function by DPLL Algorithms
- Introduction
- Preliminaries
- DPLL Algorithms
- Expanders
- Goldreich's Function
- Formulas from Goldreich's Function
- Almost Bijective Goldreich's Function
- Linear Function
- Slightly Nonlinear Goldreich's Function
- Lower Bound on Unsatisfiable Formulas
- Lower Bound on Satisfiable Formulas
- Closure
- Clever Myopic Algorithm
- References
- Gate Elimination for Linear Functions and New Feebly Secure Constructions
- Introduction
- Preliminaries
- Gate Elimination for Linear Functions
- A New Linear Feebly Secure Trapdoor Function
- Nonconstructive Bounds for Linear Functions
- Conclusion
- References
- Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas
- Introduction
- Recognition vs. Construction vs. Sampling
- The Graph Isomorphism Problem in 1979: A Las Vegas Algorithm
- Recognition vs. Sampling
- Tower of Groups
- Applications
- ``Tower of Groups'' Derandomized
- Ignorance Is Bliss
- Permutation Groups in NC
- Matrix Group Membership
- Black-Box Groups
- Nondeterministic Complexity of Membership
- Nondeterministic Complexity of Nonmembership. Arthur-Merlin Games, Almost-NP
- Randomization Tools
- Cryptographic Barriers
- The BB Filtration
- Constructive Membership Test. Center
- Statistical Group Theory
- Prequel: Leningrad, November 4, 1978
- Ten Rubles Extra
- Cylinder Intersection
- Las Vegas in Montreal
- References
- On Maltsev Digraphs
- Introduction
- Preliminaries
- Algebra
- Graph Theory
- Retracts of Maltsev Digraphs
- Characterisations, Polymorphisms and Algorithms
- Rectangular Characterisations and Other Polymorphisms
- Conservative 2-Semilattice Polymorphisms
- A Simple Inductive Construction of Maltsev DAGs
- Some Applications to the Constraint Satisfaction Problem
- References
- Join-Reachability Problems in Directed Graphs
- Introduction
- Preprocessing: Computing Layers and Removing Cycles
- Computational Complexity
- Combinatorial Complexity
- Two Paths
- Tree and Path
- Two Trees
- Unoriented Trees
- Planar Digraphs
- General Digraphs
- Data Structures
- Conclusions and Open Problems
- References
- Graphs of Bounded Treewidth Can Be Canonized in AC1
- Introduction
- Preliminaries
- Canonization of Graphs of Bounded Treewidth
- Pre-ordering for Canonization and Valid Child Bags
- Minimal Description for Graphs of Bounded Treewidth
- Complexity Analysis
- The Canonization
- References
- Snakes and Cellular Automata: Reductions and Inseparability Results
- Introduction
- Definitions
- Tilings
- Cellular Automata
- Directed Tiles and Paths
- Snake Tiling Problems
- Inseparability Results
- Conclusions
- References
- Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width
- Introduction
- Definitions and Notation
- Supergroup Partitions Characterise Clique-Width
- The Clique-Width of Large Path Powers
- Final Remarks
- References
- An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents
- Introduction
- Basic Notions
- Triangular Tree-Width
- A Guiding Example
- Computing Permanents of Matrices of Bounded ttw
- Particular Case: Perfect Triangular Decompositions
- The General Case
- Efficiently Solving Subclasses of Hamiltonian Cycle
- Open Questions
- References
- Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
- Introduction
- The Polynomially Solvable Cases of Theorem 1
- Parameterized Complexity
- The NP-Complete Cases of Theorem 1
- Future Research
- References
- Compressed Membership in Automata with Compressed Labels
- Introduction
- Preliminaries
- A Deterministic Algorithm
- A Nondeterministic Algorithm
- Compressed Unary Labels
- Some Combinatorics on Words
- Proof of Theorem 4
- Conclusion
- References
- Locally Decodable Codes
- References
- Precedence Automata and Languages
- Introduction
- Preliminaries
- Floyd Automata
- Floyd Automata vs. Floyd Grammars
- From Floyd Grammars to Floyd Automata
- From Floyd Automata to Floyd Grammars
- $\omega$-Languages
- Conclusions and Further Research
- References
- Orbits of Linear Maps and Regular Languages
- Preliminaries
- Decidable Variations of PB-Realizability Problem
- An Undecidable Problem
- References
- Shared-Memory Systems and Charts
- Communication with Shared Variables
- Shared-Memory Systems
- Partial-Order Semantics of Shared-Memory Systems
- Asynchronous Automata and Zielonka's Theorem
- Expressive Power of Shared-Memory Systems
- Cut-Bounded Languages
- Refinements of Cut-Bounded Languages
- Büchi's Theorem for Cut-Bounded Languages
- Generalizations of Zielonka's Theorem
- Shared-Memory Charts
- Gates and Shared-Memory Charts
- Asynchronous Product of Shared-Memory Charts
- Checking Cut-Boundedness of an SMC Specification
- Loop-Connected SMC Specifications
- Related Work
- References
- On the CSP Dichotomy Conjecture
- Introduction
- CSP, Homomorphisms, Logic
- CSP vs. MMSNP, Dichotomy
- Algorithmic Approaches
- Propagation Algorithms
- Gaussian Elimination
- Logic Characterizations
- Algebraic Background
- Polymorphisms
- Algebras
- Algebras and Algorithms
- Datalog and Bounded Width
- Gaussian Elimination and Few Subpowers
- Combining the Two Approaches
- References
- LR(0) Conjunctive Grammars and Deterministic Synchronized Alternating Pushdown Automata
- Introduction
- Preliminaries
- Conjunctive Grammars
- Synchronized Alternating Pushdown Automata
- Deterministic SAPDA Model Definition
- Linear Membership for DSAPDA
- LR(0) Conjunctive Grammars
- Constructing an LR(0) Grammar from a DSAPDA
- Concluding Remarks
- References
- Two-Way Automata versus Logarithmic Space
- Introduction
- Preparation
- Machines
- Reductions
- The Berman-Lingas Theorem
- Conclusion
- References
- A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row
- Introduction
- Preliminaries
- Finding an MCSR Involving a Given Row
- MIk Tucker Configurations
- MIIIk Tucker Configurations
- MIIk Tucker Configurations
- MIV and MV Tucker Configurations
- Summing Up
- Applying Our Framework to Related Problems
- References
- Two Combinatorial Criteria for BWT Images
- Introduction to BWT
- Definitions and Preliminaries
- BWT and Structure of Permutations
- Block Structure of BWT Images
- References
- Recent Results on Polynomial Identity Testing
- References
- Towards Approximate Matching in Compressed Strings: Local Subsequence Recognition
- Introduction
- General Techniques
- Preliminaries
- Semi-local LCS
- Alignment Dags and Score Matrices
- Score Matrix Composition
- Subsequences in Compressed Strings
- Three-Way Semi-local LCS
- Local Subsequence Recognition
- Conclusions
- References
- The Optimal Strategy for the Average Long-Lived Consensus
- Introduction
- Average Instability
- Framework
- The Result
- The Auxiliary Process and Its Optimal Strategy
- The Auxiliary Process
- Trajectory Colorings
- Analysis of the Auxiliary Process
- From the Auxiliary Process to the Original Process
- Extensions
- Infinite Memory
- Other Probability Distributions
- References
- Improved Online Scheduling in Maximizing Throughput of Equal Length Jobs
- Introduction
- Related Work
- Our Contribution
- Preliminaries
- A 4.24-Competitive Algorithm for Preemption with Restart
- A 4.24-Competitive Algorithm for Preemption with Resume
- References
- Recognizing Sparse Perfect Elimination Bipartite Graphs
- Introduction
- Perfect Elimination Bipartite Graphs
- Goh-Rotem on Sparse Instances
- Avoiding Matrix Multiplication
- Discussion
- Conclusion
- References
- A Multiple-Conclusion Calculus for First-Order Gödel Logic
- Introduction
- Preliminaries
- Proof-Theoretical Preliminaries
- Semantic Preliminaries
- The Multiple-Conclusion System
- Soundness, Completeness and Cut-Admissibility
- Cut-Admissibility for HIF
- Further Research
- References
- Author Index
