Time filter

Source Type

Kulikov A.S.,Steklov Institute Of Mathematics At St Petersburg | Melanich O.,Steklov Institute Of Mathematics At St Petersburg | Mihajlin I.,Saint Petersburg State Polytechnic University
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | Year: 2012

We give a simple proof of a 5n - o(n) lower bound on the circuit size over U 2 of a linear function f(x) = Ax where A ε {0,1} log n x n (here, U 2 is the set of all Boolean binary functions except for parity and its complement). © 2012 Springer-Verlag.


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.


Hirsch E.A.,Steklov Institute Of Mathematics At St Petersburg | Itsykson D.,Steklov Institute Of Mathematics At St Petersburg
Leibniz International Proceedings in Informatics, LIPIcs | Year: 2010

The existence of a (p-)optimal propositional proof system is a major open question in (proof) complexity; many people conjecture that such systems do not exist. Krajíček and Pudlák [KP89] show that this question is equivalent to the existence of an algorithm that is optimal1 on all propositional tautologies. Monroe [Mon09] recently gave a conjecture implying that such algorithm does not exist. We show that in the presence of errors such optimal algorithms do exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow the algorithm to claim a small number of false "theorems" (according to any polynomial-time samplable distribution on non-tautologies) and err with bounded probability on other inputs. Our result can also be viewed as the existence of an optimal proof system in a class of proof systems obtained by generalizing automatizable proof systems. © E. A. Hirsch and D. Itsykson.


Hirsch E.A.,Steklov Institute Of Mathematics At St Petersburg | Itsykson D.,Steklov Institute Of Mathematics At St Petersburg | Monakhov I.,Steklov Institute Of Mathematics At St Petersburg | Smal A.,Steklov Institute Of Mathematics At St Petersburg
Theory of Computing Systems | Year: 2012

The existence of an optimal propositional proof system is a major open question in proof complexity; many people conjecture that such systems do not exist. Krajíček and Pudlák (J. Symbol. Logic 54(3):1063, 1989) show that this question is equivalent to the existence of an algorithm that is optimal on all propositional tautologies. Monroe (Theor. Comput. Sci. 412(4-5):478, 2011) recently presented a conjecture implying that such an algorithm does not exist. We show that if one allows errors, then such optimal algorithms do exist. The concept is motivated by the notion of heuristic algorithms. Namely, we allow an algorithm, called a heuristic acceptor, to claim a small number of false "Theorems" and err with bounded probability on other inputs. The amount of false "Theorems" is measured according to a polynomial-time samplable distribution on non-tautologies. Our result remains valid for all recursively enumerable languages and can also be viewed as the existence of an optimal weakly automatizable heuristic proof system. The notion of a heuristic acceptor extends the notion of a classical acceptor; in particular, an optimal heuristic acceptor for any distribution simulates every classical acceptor for the same language. We also note that the existence of a co-NP-language L with a polynomial-time samplable distribution on L̄ that has no polynomial-time heuristic acceptors is equivalent to the existence of an infinitely-often one-way function. © 2011 Springer Science+Business Media, LLC.


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.


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.


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 | Slabodkin M.,St Petersburg Academic University | Sokolov D.,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

The resolution complexity of the perfect matching principle was studied by Razborov [Raz04], who developed a technique for proving its lower bounds for dense graphs. We construct a constant degree bipartite graph Gn such that the resolution complexity of the perfect matching principle for Gn is 2Ω(n), where n is the number of vertices in Gn. This lower bound is tight up to some polynomial. Our result implies the 2Ω(n) lower bounds for the complete graph K2n+1 and the complete bipartite graph Kn,O(n) that improves the lower bounds following from [Raz04]. Our results also imply the well-known exponential lower bounds on the resolution complexity of the pigeonhole principle, the functional pigeonhole principle and the pigeonhole principle over a graph. We also prove the following corollary. For every natural number d, for every n large enough, for every function h : {1, 2, ..., n} → {1, 2, ..., d}, we construct a graph with n vertices that has the following properties. There exists a constant D such that the degree of the i-th vertex is at least h(i) and at most D, and it is impossible to make all degrees equal to h(i) by removing the graph’s edges. Moreover, any proof of this statement in the resolution proof system has size 2Ω(n). This result implies well-known exponential lower bounds on the Tseitin formulas as well as new results: for example, the same property of a complete graph. © Springer International Publishing Switzerland 2015.


Itsykson D.,Steklov Institute Of Mathematics At St Petersburg | Sokolov D.,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: 2011

The paper is devoted to lower bounds on the time complexity of DPLL algorithms that solve the satisfiability problem using a splitting strategy. Exponential lower bounds on the running time of DPLL algorithms on unsatisfiable formulas follow from the lower bounds for resolution proofs. Lower bounds on satisfiable instances are also known for some classes of DPLL algorithms; this lower bounds are usually based on reductions to unsatisfiable instances. In this paper we consider DPLL algorithms with a cut heuristic that may decide that some branch of the splitting tree will not be investigated. DPLL algorithms with a cut heuristic always return correct answer on unsatisfiable formulas while they may err on satisfiable instances. We prove the theorem about effectiveness vs. correctness trade-off for deterministic myopic DPLL algorithms with cut heuristic. Myopic algorithms can see formulas with erased signs of negations; they may also request a small number of clauses to read them precisely. We construct a family of unsatisfiable formulas Φ (n) and a polynomial time samplable ensemble of distributions Q n concentrated on satisfiable formulas such that every deterministic myopic algorithm that gives a correct answer with probability 1-o(1) on a random formula from the ensemble Q n runs exponential time on the formulas Φ (n). © 2011 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.

Loading Steklov Institute Of Mathematics At St Petersburg collaborators
Loading Steklov Institute Of Mathematics At St Petersburg collaborators