

On optimal heuristic randomized semidecision procedures, with application to proof complexity
Talk was presented at
27th International Symposium on Theoretical Aspects of Computer Science (STACS),
Nancy, France, March 46, 2010.

Structutal complexity of AvgBPP
Talk was presented at
4th International Computer Science Symposium in Russia, Novosibirsk, 2009

Averagecase complexity of randomized computations with bounded error
Talk was presented at
14th Estonian Winter School in Computer Science (EWSCS), Palmse, Estonia,
March 16, 2009.
An infinitlyoften oneway function based on averagecase assumption.
Talk was presented at
15th Workshop on Logic, Language, Information and Computation (WoLLIC)
July 1st to 4th, 2008, Edinburgh, Scotland
Oneway function based on averagecase assumption.
Talk was presented at
Workshop on Computational, Descriptive and Proof Complexity,
and Algorithms, Independent University of Moscow, Russia, August 2931, 2007

Derandomization: main approaches and results.
Lecture 1: One side error and dispersers. (slides in russian)
Lectures 23: Two side error, majority dispersers and extractors, Trevisan extractor. (slides in russian)
Lecture 4: Pseudorandom generators. (slides in russian)
Exponential Lower Bound for treelike LovaszSchrijver proof systems.
Talk was presented at
Dagstuhl Seminar 06401, Complexity of constraints, Germany, Dagstuhl Schloss, October 16, 2006

Exponential lower bounds for the
running time of DPLL algorithms
for SAT on satisfiable formulas.
Talk was presented at
10th Estonian Winter School in Computer Science (EWSCS), Palmse, Estonia,
February 27  March 4, 2005.
