Page last modified: March 1st, 2009

WORKSHOP ON ALGEBRA, COMBINATORICS AND COMPLEXITY

Supported by Russian Foundation for Basic Research and Indian Ministry of Science and Technology

Ekaterinburg, Ural State University, September 30th –October 4th, 2008

PROGRAM (with links to all scientific presentations)

OCTOBER 1ST, WEDNESDAY

 

10:00-10:30

OPENING, greetings by Mr S.K. Varshney, Counsellor (Science & Technology) of Embassy of India in Moscow, and by Prof. V.E. Tret'jakov, President of Ural State University

10:30-11:25

1ST LECTURE: Meena Mahajan: Small-width arithmetic circuits

11:30-12:00

Coffee break

12:00-12:40

1ST STUDENT PRESENTATION: Pavel Egorov: Extensible syntax analysers (pdf)

12:45-13:25

2ND STUDENT PRESENTATION: Benny George Kenkireth: On conjugacy of pairs and triples. I. Introduction to  combinatorics on words

13:30-15:00

Break for lunch and informal discussion

15:00-15:55

2ND LECTURE: Arseny Shur: Threshold languages: structure and growth

16:00-16:30

Coffee break

16:30-17:10

3RD STUDENT PRESENTATION: Nutan Limaye: Interplay between language classes and complexity classes

17:15-17:55

4TH STUDENT PRESENTATION: Prajakta Nimbhorkar: Planar Graph Isomorphism is complete for Logspace

18:30-…

Reception

 



OCTOBER 2ND, THURSDAY

 

09:00-12:30

Excursion

13:00-14:30

Break for lunch and informal discussion

14:30-15:25

3RD LECTURE: Kamal Lodaya: Deterministic expressions and unambiguous logic

15:30-15:55

5TH STUDENT PRESENTATION : Grigoriy Povarov: Finite transducers and nondeterministic state complexity

16:00-16:25

6TH STUDENT PRESENTATION: Mikhail Berlinkov: Inapproximability of length of minimal synchronizing words

16:30-17:00

Coffee break

17:00-19:00

Joint meeting with the seminar "Algebraic Systems"

17:00-17:55

Lev Shevrin: On the Seminar "Algebraic Systems"

18:00-18:55

Meena Mahajan: Theoretical Computer Science in Chennai

 

OCTOBER 3RD, FRIDAY

 

09:30-10:25

4TH LECTURE: Samir Datta: Deterministically isolating a perfect matching in bipartite planar graphs

10:30-11:25

5TH LECTURE: Vladimir Popov: Theory of actions, robot control and semigroups (pdf)

11:30-12:00

Coffee break

12:00-12:40

7TH STUDENT PRESENTATION: M. Praveen: Analyzing reachability for some Petri nets with fast growing markings

12:45-13:25

8TH STUDENT PRESENTATION: Elena Pribavkina: Finitely generated synchronizing automata

13:30-15:00

Break for lunch and informal discussion

15:00-15:55

6TH LECTURE: Mikhail Volkov: Careful synchronization of partial automata

16:00-16:30

Coffee break

16:30-17:10

9TH STUDENT PRESENTATION: Benny George Kenkireth: On conjugacy of pairs and triples. II. On solving language equations

17:15-17:55

10TH STUDENT PRESENTATION: Alexei Khvorost: Algorithms on compressed strings

18:30-…

The ballet “The Tale of the Stone Flower” (Academic Opera and Ballet Theater)