Computer Science -- Theory and Applications
7th International Computer Science Symposium in Russia, CSR 2012, Niszhny Novgorod, Russia, July 3-7, 2012, Proceedings
Published on 11. August 2012
XXIII, 327 pages
978-3-642-30642-6 (ISBN)
Description
This book constitutes the proceedings of the 7th International Computer Science Symposium in Russia, CSR 2012, held in Nizhny Novgorod in July 2012. The 28 full papers presented in this volume were carefully reviewed and selected from 66 submissions. CSR 2012 was one of the events of the Alan Turing Year 2012, the topics dealt with cover substantial parts of theoretical computer science and its applications.
More details
Other editions
Additional editions
Edward Hirsch | Juhani Karhumäki | Arto Lepistö
Computer Science -- Theory and Applications
7th International Computer Science Symposium in Russia, CSR 2012, Niszhny Novgorod, Russia, July 3-7, 2012, Proceedings
Book
05/2012
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title Page
- Preface
- Organization
- Table of Contents
- Opening Talk
- Can the Theory of Algorithms Ratify the ``Invisible Hand of the Market''?
- Introduction
- References
- Full Papers
- Resilient Quicksort and Selection
- Introduction
- Preliminaries
- Previous Work
- Our Contribution
- Randomized Sorting
- Resilient Selection
- Deterministic Sorting
- References
- General Quantitative Specification Theories with Modalities
- Introduction
- Structured Modal Transition Systems
- Refinement Distances
- Structural Composition and Quotient
- Conjunction
- Conclusion
- References
- The Complexity of Intersecting Finite Automata Having Few Final States
- Introduction
- Our Contribution
- Preliminaries
- Basic Definitions and Notation
- Problems
- Groups and Abelian Groups
- Some Observations on Commutative Monoids
- Conclusion and Further Work
- News about Semiantichains and Unichain Coverings
- Introduction
- Constructions
- A Bad Example
- Checking Tests for Read-Once Functions over Arbitrary Bases
- Introduction
- Background and Related Work
- Basic Definitions
- The Relevance Hypercube Method
- Assumptions and Notation
- Some Observations
- Auxiliary Lemmas
- Main Theorem
- Discussion
- Approximating Minimum Power Edge-Multi-Covers
- Introduction
- Motivation and Problems Considered
- Our Results
- Overview of the Techniques
- Proof of Theorem 1
- Reduction to Bipartite Graphs
- An O(logk)-Approximation Algorithm for General Costs
- A Constant Ratio Approximation Algorithm for Unit Costs
- Proof of Theorem 2
- Conclusions and Open Problems
- A Lower Bound on Circuit Complexity of Vector Function in U2
- Introduction
- New Lower Bound
- Computing All MOD-Functions Simultaneously
- Introduction
- Preparations
- Basic Facts from Number Theory
- Encodings
- Building Blocks
- Upper Bounds
- C(ALLMODrn) = O(n)
- C(ALLMODr1, ., rnn) = O(n loglogn)
- Further Directions
- Bounded Synchronization Delay in Omega-Rational Expressions
- Introduction
- Preliminaries
- Local Divisors
- Schützenberger's Class SD
- SD Equals AP
- Finitely Many c
- Infinitely Many c
- SD= AP Implies SF= AP
- Towards Optimal Degree-Distributions for Left-Perfect Matchings in Random Bipartite Graphs
- Introduction
- Motivation and Related Work
- Results
- Optimality of Concentration in a Unit Length Interval
- Average Degrees of Different Nodes are Close
- Optimal Distributions Use Only Two Neighboring Degrees
- A Conjecture: Essentially Two Different Strategies
- Conclusion
- Robust Sensor Range for Constructing Strongly Connected Spanning Digraphs in UDGs
- Introduction
- Related Work
- Results and Outline of the Paper
- Robustness of Unit Disk Graphs
- Efficiently Computing Weak t-Robustness
- Digraph with Max Out-Degree Four
- Digraph with Max Out-Degree Three
- Conclusion
- Worst-Case Optimal Priority Queues via Extended Regular Counters
- Introduction
- Description of the Data Structure
- Priority-Queue Operations
- Violation Reductions
- Extended Regular Binary Counters
- Conclusions
- The Complexity of Minor-Ancestral Graph Properties with Forbidden Pairs
- Introduction
- Main Result
- Discussion
- Deciding Membership in co-FSP
- Forbidden Edge Pairs
- Fixed Parameter Tractability
- Conclusions
- Satisfiability Thresholds beyond k-XORSAT
- Introduction
- Contribution
- Motivation
- Notation and Basics for the12mumod3-Case
- Structure of the Proof of Theorem 5
- Structure of the Proof of Theorem 9
- Uniquely Extendible Constraints
- Finding Vertex-Surjective Graph Homomorphisms
- Introduction
- Definitions and Preliminaries
- Hard Cases
- Tractable Cases
- Conclusions
- Broadcast Domination on Block Graphs in Linear Time
- Introduction
- Definitions and Notation
- General Properties of Dominating Broadcasts
- Structural Properties of Dominating Broadcasts on Block Graphs
- Algorithmic Properties of Dominating Broadcasts on Block Graphs
- A Linear-time Algorithm for Optimal Broadcasts on Block Graphs
- Concluding Remarks
- Characterizing Certain Topological Specifications
- Introduction
- The Languages We Consider
- Saturation
- Bisimulations
- The Characterization Theorem
- Concluding Remarks
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- Introduction
- Preliminaries
- Optimal Simulation of AFAs by NFAs
- Boolean and Alternating State Complexity of Basic Regular Operations
- Conclusions
- Consistency of Multidimensional Combinatorial Substitutions
- Introduction
- Definitions
- Undecidability Results
- Undecidability of Consistency
- Undecidability of Overlapping
- Decidability Results
- Decidability of Consistency for Domino-Complete Substitutions
- Decidability of Overlapping for Consistent Domino-Complete Substitutions
- Conclusion and Open Problems
- Two-Way Automata Characterizations of L/poly versus NL
- Introduction
- Preparation
- Automata
- Problems
- Transducers, Reductions, and Completeness
- Closures
- Characterizations and Conjectures
- Conclusion
- Cutting through Regular Post Embedding Problems
- Introduction
- Basic Notation and Definitions
- Deciding PEP partialdir, or PEP with Partial Directness
- Counting the Number of Solutions
- Universal Variants of PEP partialdir
- Undecidability for PEP co&dir and Other Extensions
- Concluding Remarks
- On the Advice Complexity of the Set Cover Problem
- Introduction and Preliminaries
- Bounds Measured in the Size of X
- Bounds Measured in the Size of S
- Conclusion
- Constraint Satisfaction with Counting Quantifiers
- Introduction
- Preliminaries
- Game Characterisation
- Complexity of a Single Quantifier
- Counting Quantifiers on Cliques and Cycles
- Cliques: Proof of Theorem 1
- Cycles: Proof of Theorem 2
- Extensions of the CSP
- Bipartite Graphs
- The Complexity of QCSP(C*4)
- Conclusion
- Space-Bounded Kolmogorov Extractors
- Introduction
- Preliminaries
- Kolmogorov Complexity
- Extractors
- Balanced Tables
- Nisan-Wigderson Generators
- Constant-depth Circuits for Approximate Counting
- Main Result
- Overview
- Proof Idea
- Derandomization Plan
- The Weakening of Balancing Conditions
- Existence of Balanced Tables in the Output of the NW-generator
- Searching for a Good Seed
- Completion of the Proof
- Some Results on more Flexible Versions of Graph Motif
- Introduction
- Maximizing the Solution Size
- Minimizing the Number of Substitutions
- Using Modularity
- Definitions and Properties
- When Modules Join Graph Motif
- Difficulty of the Problem
- Algorithms for the Decision Problem
- Open Problems
- A Characterization of Cellular Automata Generated by Idempotents on the Full Shift
- Introduction
- Definitions and Useful Lemmas
- Cellular Automata Generated by Idempotents on the Full Shift
- Forbidding a Word from the Input: E
- Encoding Aperiodic Parts and Memorizing Periodic Parts: A
- Periodic Subwords of Small Enough Period: P
- The Final Touch: F
- Examples and Decidability Questions
- Examples
- Decidability Questions
- Constructing Polynomials for Functions over Residue Rings Modulo a Composite Number in Linear Time
- Introduction
- Concepts
- On Some Characteristics of Monomials
- Canonical form of Polynomials
- Checking Algorithm of Polynomiality for Functions
- Boolean Composition of Visual Secret Sharing Schemes
- Introduction
- Definitions, Notations and Facts
- Visual Secret Sharing Schemes
- Contrast as Objective Function in a Linear Program
- The Composition of Two Access Structures
- Conjunction of Two Threshold-Schemes
- Proof of Claim 1
- Proof of Claim 2
- Author Index
