Computer Science - Theory and Applications

Name: Computer Science - Theory and Applications | 6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

6th International Computer Science Symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14-18, 2011. Proceedings

Alexander Kulikov Nikolay Vereshchagin(Herausgeber*in)

Springer (Verlag)

Erschienen am 12. Juni 2011

XI, 471 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-20712-9 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken