|
|
-
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 4-6, 2010.
-
Structutal complexity of AvgBPP
Talk was presented at
4th International Computer Science Symposium in Russia, Novosibirsk, 2009
-
Average-case complexity of randomized computations with bounded error
Talk was presented at
14th Estonian Winter School in Computer Science (EWSCS), Palmse, Estonia,
March 1-6, 2009.
An infinitly-often one-way function based on average-case assumption.
Talk was presented at
15th Workshop on Logic, Language, Information and Computation (WoLLIC)
July 1st to 4th, 2008, Edinburgh, Scotland
One-way function based on average-case assumption.
Talk was presented at
Workshop on Computational, Descriptive and Proof Complexity,
and Algorithms, Independent University of Moscow, Russia, August 29-31, 2007
-
Derandomization: main approaches and results.
Lecture 1: One side error and dispersers. (slides in russian)
Lectures 2-3: Two side error, majority dispersers and extractors, Trevisan extractor. (slides in russian)
Lecture 4: Pseudorandom generators. (slides in russian)
Exponential Lower Bound for tree-like Lovasz-Schrijver proof systems.
Talk was presented at
Dagstuhl Seminar 06401, Complexity of constraints, Germany, Dagstuhl Schloss, October 1-6, 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.
|
