Constitutes the refereed proceedings of the Second International Symposium on Computer Science in Russia, CSR 2007, held in Ekaterinburg, Russia, September 3-7, 2007. This book presents 35 revised papers that were reviewed and selected from 95 submissions.

Proving Church’s Thesis.- The Limits of Quantum Computers.- Marrying Words and Trees.- TPTP, TSTP, CASC, etc..- Abstract Modeling and Formal Verification of Microprocessors.- Sequences of Level 1, 2, 3,..., k,....- Timers and Proximities for Mobile Ambients.- Pushing Random Walk Beyond Golden Ratio.- Reversible Machine Code and Its Abstract Processor Architecture.- A Fast Algorithm for Path 2-Packing Problem.- Decidability of Parameterized Probabilistic Information Flow.- Inverting Onto Functions and Polynomial Hierarchy.- Proved-Patterns-Based Development for Structured Programs.- Planarity, Determinants, Permanents, and (Unique) Matchings.- Equivalence Problems for Circuits over Sets of Natural Numbers.- Bouillon: A Wiki-Wiki Social Web.- A PDL-Like Logic of Knowledge Acquisition.- Resource Placement in Networks Using Chromatic Sets of Power Graphs.- Conjunctive Grammars over a Unary Alphabet: Undecidability and Unbounded Growth.- Ruling Out Polynomial-Time Approximation Schemes for Hard Constraint Satisfaction Problems.- New Bounds for MAX-SAT by Clause Learning.- Towards Hierarchical Clustering (Extended Abstract).- Estimation of the Click Volume by Large Scale Regression Analysis.- Maximal Intersection Queries in Randomized Graph Models.- A Note on Specialization of Interpreters.- Efficient Computation in Groups Via Compression.- Constructing a Secret Binary Partition of a Digital Image Robust to a Loss of Synchronization.- On the Complexity of Matrix Rank and Rigidity.- On the Usage of Clustering for Content Based Image Retrieval.- Performance Modeling of Wormhole Hypermeshes Under Hotspot Traffic.- Application of Modified Coloured Petri Nets to Modeling and Verification of SDL Specified Communication Protocols.- Symmetry of Information and Nonuniform LowerBounds.- Perceptrons of Large Weight.- A Padding Technique on Cellular Automata to Transfer Inclusions of Complexity Classes.- Kolmogorov Complexity, Lovász Local Lemma and Critical Exponents.- Generic Complexity of Presburger Arithmetic.- Everywhere ?-Repetitive Sequences and Sturmian Words.- Timed Traces and Strand Spaces.- On Empirical Meaning of Randomness with Respect to a Real Parameter.- An Efficient Algorithm for Zero-Testing of a Lacunary Polynomial at the Roots of Unity.- Generic Complexity of Undecidable Problems.