Home

One-day Workshop on Complexity of Algorithms, Proofs, and Circuits

Thu, 2010-10-21

One-day Workshop on Complexity of Algorithms, Proofs, and Circuits was held in the laboratory. The workshop was chaired by Dima Grigoriev.

Program schedule

Thursday, October 21
Seminar begins10:00
Eugene DemenkovAlgebraic proofs of noncommutative formulae10:00
Dmitry Grigoriev Solving tropical linear systems11:00
Coffee break12:00
Alexander Kulikov A 3n-o(n) lower bound on the circuit complexity of affine dispersers12:30
Lunch13:30
Dmitry ItsyksonHeuristic acceptors14:30
Alexander SmalHeuristic proof systems15:30
Coffee break16:15
Dmitry Sokolov Inverting the explicit Goldreich's function with DPLL algorithms16:30
Open discussion17:30