Hirsch E.A.,Steklov Institute Of Mathematics At St Petersburg
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2010
Unless we resolve the P vs NP question, we are unable to say whether there is an algorithm (acceptor) that accepts Boolean tautologies in polynomial time and does not accept non-tautologies (with no time restriction). Unless we resolve the co-NP vs NP question, we are unable to say whether there is a proof system that has a polynomial-size proof for every tautology. In such a situation, it is typical for complexity theorists to search for "universal" objects; here, it could be the "fastest" acceptor (called optimal acceptor) and a proof system that has the "shortest" proof (called optimal proof system) for every tautology. Neither of these objects is known to the date. In this survey we review the connections between these questions and generalizations of acceptors and proof systems that lead or may lead to universal objects. © 2010 Springer-Verlag.
Itsykson D.,Steklov Institute Of Mathematics At St Petersburg |
Sokolov D.,St Petersburg Academic University
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2011
The Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by the fixed predicate of arity d. Every Goldreich's function is defined by it's dependency graph G and predicate P. In 2000 O. Goldreich formulated a conjecture that if G is an expander and P is a random predicate of arity d then the corresponding function is one way. In 2005 M. Alekhnovich, E. Hirsch and D. Itsykson proved the exponential lower bound on the complexity of inversion of Goldreich's function based on linear predicate and random graph by myopic DPLL agorithms. In 2009 J. Cook, O. Etesami, R. Miller, and L. Trevisan extended this result to nonliniar predicates (but for a slightly weaker definition of myopic algorithms). Recently D. Itsykson and independently R. Miller proved the lower bound for drunken DPLL algorithms that invert Goldreich's function with nonlinear P and random G. All above lower bounds are randomized. The main contribution of this paper is the simpler proof of the exponential lower bound of the Goldreich's function inversion by myopic DPLL algorithms. A dependency graph in our construction may be based on an arbitrary expander, particulary it is possible to use an explicit expander; the predicate may be linear or slightly nonlinear. Our definition of myopic algorithms is more general than one used by J. Cook et al. Our construction may be used in the proof of lower bound for drunken algorithms as well. © 2011 Springer-Verlag Berlin Heidelberg.
Knop A.,Steklov Institute Of Mathematics At St Petersburg
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2015
Santhanam (2007) proved that MA/1 does not have circuits of size nk. We translate his result to the average-case setting by proving that there is a constant a such that for any k, there is a language in AvgMA that cannot be solved by circuits of size nk on more than the (Formula Presented.) fraction of inputs. In order to get rid of the non-uniform advice, we supply the inputs with the probability threshold that we use to determine the acceptance. This technique was used by Pervyshev (2007) for proving a time hierarchy for heuristic computations. © Springer International Publishing Switzerland 2015.
Itsykson D.,Steklov Institute Of Mathematics At St Petersburg
Theory of Computing Systems | Year: 2014
We prove an exponential lower bound on the average time of inverting Goldreich's function by drunken backtracking algorithms; this resolves the open question stated in Cook et al. (Proceedings of TCC, pp. 521-538, 2009). The Goldreich's function has n binary inputs and n binary outputs. Every output depends on d inputs and is computed from them by the fixed predicate of arity d. Our Goldreich's function is based on an expander graph and on the nonlinear predicates that are linear in Ω(d) variables. Drunken algorithm is a backtracking algorithm that somehow chooses a variable for splitting and randomly chooses the value for the variable to be investigated at first.After the submission to the journal we found out that the same result was independently obtained by Rachel Miller. © 2013 Springer Science+Business Media New York.
Gravin N.,Nanyang Technological University |
Gravin N.,Steklov Institute Of Mathematics At St Petersburg |
Lasserre J.,CNRS Laboratory for Analysis and Architecture of Systems |
Pasechnik D.V.,Nanyang Technological University |
Robins S.,Nanyang Technological University
Discrete and Computational Geometry | Year: 2012
We present a general and novel approach for the reconstruction of any convex d-dimensional polytope P, assuming knowledge of finitely many of its integral moments. In particular, we show that the vertices of an N-vertex convex polytope in ℝ d can be reconstructed from the knowledge of O(DN) axial moments (w. r. t. to an unknown polynomial measure of degree D), in d+1 distinct directions in general position. Our approach is based on the collection of moment formulas due to Brion, Lawrence, Khovanskii-Pukhlikov, and Barvinok that arise in the discrete geometry of polytopes, combined with what is variously known as Prony's method, or the Vandermonde factorization of finite rank Hankel matrices. © 2012 Springer Science+Business Media, LLC.