|
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
| 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 |
|
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 |