Computer Science – Theory and Applications

1. Front Matter

   PDF

2. The Equivalence of Sampling and Searching

   • Scott Aaronson

   Pages 1-14

3. Towards a Complexity Theory of Randomized Search Heuristics: Ranking-Based Black-Box Complexity

   • Benjamin Doerr, Carola Winzen

   Pages 15-28

4. Learning Read-Constant Polynomials of Constant Degree Modulo Composites

   • Arkadev Chattopadhyay, Ricard Gavaldà, Kristoffer Arnsfelt Hansen, Denis Thérien

   Pages 29-42

5. On the Arithmetic Complexity of Euler Function

   • Manindra Agrawal

   Pages 43-49

6. Pseudo-random Graphs and Bit Probe Schemes with One-Sided Error

   • Andrei Romashchenko

   Pages 50-63

7. Improving the Space-Bounded Version of Muchnik’s Conditional Complexity Theorem via “Naive” Derandomization

   • Daniil Musatov

   Pages 64-76

8. The Complexity of Solving Reachability Games Using Value and Strategy Iteration

   • Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen, Peter Bro Miltersen

   Pages 77-90

9. Faster Polynomial Multiplication via Discrete Fourier Transforms

   • Alexey Pospelov

   Pages 91-104

10. Kolmogorov Complexity as a Language

    • Alexander Shen

    Pages 105-119

11. Almost k-Wise Independent Sets Establish Hitting Sets for Width-3 1-Branching Programs

    • Jiří Šíma, Stanislav Žák

    Pages 120-133

12. The Complexity of Inversion of Explicit Goldreich’s Function by DPLL Algorithms

    • Dmitry Itsykson, Dmitry Sokolov

    Pages 134-147

13. Gate Elimination for Linear Functions and New Feebly Secure Constructions

    • Alex Davydow, Sergey I. Nikolenko

    Pages 148-161

14. Finite Groups and Complexity Theory: From Leningrad to Saint Petersburg via Las Vegas

    • László Babai

    Pages 162-180

15. On Maltsev Digraphs

    • Catarina Carvalho, László Egri, Marcel Jackson, Todd Niven

    Pages 181-194

16. Join-Reachability Problems in Directed Graphs

    • Loukas Georgiadis, Stavros D. Nikolopoulos, Leonidas Palios

    Pages 195-208

17. Graphs of Bounded Treewidth Can Be Canonized in \(\mbox{{\sf AC}$^1$}\)

    • Fabian Wagner

    Pages 209-222

18. Snakes and Cellular Automata: Reductions and Inseparability Results

    • Jarkko Kari

    Pages 223-232

19. Computing the Clique-Width of Large Path Powers in Linear Time via a New Characterisation of Clique-Width

    • Pinar Heggernes, Daniel Meister, Udi Rotics

    Pages 233-246

20. An Extended Tree-Width Notion for Directed Graphs Related to the Computation of Permanents

    • Klaus Meer

    Pages 247-260

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.

• algorithms
• automata theory
• computational complexity
• context-free languages
• decidability
• algorithm analysis and problem complexity

• Steklov Institute of Mathematics at St. Petersburg, St.Petersburg, Russia

  Alexander Kulikov

• Department of Mathematical Logic and Theory of Algorithms, Moscow State University, Moscow, Russia

  Nikolay Vereshchagin

Policies and ethics