Learning algorithms from natural proofs
Abstract Based on Hastad's (1986) circuit lower bounds, Linial, Mansour, and Nisan (1993)
gave a quasipolytime learning algorithm for AC^ 0 (constant-depth circuits with AND, OR …
gave a quasipolytime learning algorithm for AC^ 0 (constant-depth circuits with AND, OR …
Non-commutative Edmonds' problem and matrix semi-invariants
In 1967, J. Edmonds introduced the problem of computing the rank over the rational function
field of an n * nn× n matrix T with integral homogeneous linear polynomials. In this paper, we …
field of an n * nn× n matrix T with integral homogeneous linear polynomials. In this paper, we …
Constructive non-commutative rank computation is in deterministic polynomial time
We extend the techniques developed in Ivanyos et al.(Comput Complex 26 (3): 717–763,
2017) to obtain a deterministic polynomial-time algorithm for computing the non …
2017) to obtain a deterministic polynomial-time algorithm for computing the non …
Circuit complexity, proof complexity, and polynomial identity testing: The ideal proof system
JA Grochow, T Pitassi - Journal of the ACM (JACM), 2018 - dl.acm.org
We introduce a new and natural algebraic proof system, whose complexity measure is
essentially the algebraic circuit size of Nullstellensatz certificates. This enables us to exhibit …
essentially the algebraic circuit size of Nullstellensatz certificates. This enables us to exhibit …
Towards hardness of approximation for polynomial time problems
Proving hardness of approximation is a major challenge in the field of fine-grained
complexity and conditional lower bounds in P. How well can the Longest Common …
complexity and conditional lower bounds in P. How well can the Longest Common …
Algorithms based on*-algebras, and their applications to isomorphism of polynomials with one secret, group isomorphism, and polynomial identity testing
We consider two basic algorithmic problems concerning tuples of (skew-) symmetric
matrices. The first problem asks us to decide, given two tuples of (skew-) symmetric matrices …
matrices. The first problem asks us to decide, given two tuples of (skew-) symmetric matrices …
Constructive non-commutative rank computation is in deterministic polynomial time
Let {\mathcal B} be a linear space of matrices over a field {\mathbb spanned by n\times n
matrices B_1,\dots, B_m. The non-commutative rank of {\mathcal B} $ is the minimum r\in …
matrices B_1,\dots, B_m. The non-commutative rank of {\mathcal B} $ is the minimum r\in …
From independent sets and vertex colorings to isotropic spaces and isotropic decompositions: Another bridge between graphs and alternating matrix spaces
In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the
context of perfect matchings Proceedings of FCT, 1979, pp. 565--574. A similar connection …
context of perfect matchings Proceedings of FCT, 1979, pp. 565--574. A similar connection …
Polynomial Identity Testing and the Ideal Proof System: PIT is in NP if and only if IPS can be p-simulated by a Cook-Reckhow proof system
JA Grochow - arxiv preprint arxiv:2306.02184, 2023 - arxiv.org
The Ideal Proof System (IPS) of Grochow & Pitassi (FOCS 2014, J. ACM, 2018) is an
algebraic proof system that uses algebraic circuits to refute the solvability of unsatisfiable …
algebraic proof system that uses algebraic circuits to refute the solvability of unsatisfiable …
Complexity in ideals of polynomials: questions on algebraic complexity of circuits and proofs
JA Grochow - Bulletin of EATCS, 2020 - bulletin.eatcs.org
Abstract Given ideals In⊆ F [x1,... xn] for each n, what can we say about the circuit
complexity of polynomial families fn in those ideals, that is, such that fn∈ In for all n? Such …
complexity of polynomial families fn in those ideals, that is, such that fn∈ In for all n? Such …