Page last modified: June 5th, 2008

WORKSHOP ON ALGEBRA, COMBINATORICS AND COMPLEXITY

A Satellite Workshop to CSR 2008

Moscow, June 6-7, 2008

The workshop will be held in Moscow Institute of Open Education, 36 Timiryazevskaya street, 4th floor.
The Institute is situated near metro station “Timiryazevskaya“, see the map.

FINAL PROGRAM

FIRDAY, JUNE 6, 2008
13:00-14:00 Registration
14:00-14:10 OPENING

14:15-15:10

Invited talk: B. I. Plotkin, Cascade Connections and Triangular Products of Linear Automata

15:15-15:45

Coffee break

15:45-16:10

S. Obraztsova, Further Results on the Chromatic Uniqueness of K4 Homeomorphs

16:15-16:40

A. Shur, Languages with Finite Antidictionaries

16:45-17:10

I. Rystsov, Theory of general linear automata



SATURDAY, JUNE 7, 2008

09:00-09:55

Tutorial: M. Mahajan, Polynomial-size log-depth Circuits: between NC^1 and AC^1

10:00-10:25

F. Ablayev, A. Khasianov and A. Vasiliev, On Complexity of Quantum Branching Programs Computing Equality-like Boolean Functions

10:30-11:00

Coffee break

11:00-11:55 Tutorial: M. Volkov, Synchronizing Automata and the Road Coloring Theorem

12:00-12:25

P. Martyugin, Complexity of Problems Concerning Reset Words for Some Partial Cases of Automata

12:30-13:25 Invited talk: E. Allender, Kolmogorov Complexity is Circuit Complexity
13:30-14:00

Lunch