Page last modified:
|
WORKSHOP ON
ALGEBRA, COMBINATORICS AND COMPLEXITY |
|
|
Supported by Russian
Foundation for Basic Research and Indian Ministry of Science and Technology |
|
Ekaterinburg, Ural
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 |
|
|
Break for lunch and informal
discussion |
|
|
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 |
|
|
Break for lunch and informal
discussion |
|
|
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 |
|
|
10TH STUDENT PRESENTATION: Alexei Khvorost: Algorithms on compressed strings |
|
18:30-… |
The ballet “The Tale of the Stone Flower” (Academic Opera and
Ballet Theater) |