Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > HILBERT'S NULLSTELLENSATZ:
Reports tagged with Hilbert's Nullstellensatz:
TR98-067 | 12th November 1998
Paul Beame

#### Propositional Proof Complexity: Past, Present and Future

Proof complexity, the study of the lengths of proofs in
propositional logic, is an area of study that is fundamentally connected
both to major open questions of computational complexity theory and
to practical properties of automated theorem provers. In the last
decade, there have been a number of significant advances ... more >>>

TR22-106 | 21st July 2022
Suryajith Chillara, Coral Grichener, Amir Shpilka

#### On Hardness of Testing Equivalence to Sparse Polynomials Under Shifts

We say that two given polynomials $f, g \in R[x_1, \ldots, x_n]$, over a ring $R$, are equivalent under shifts if there exists a vector $(a_1, \ldots, a_n)\in R^n$ such that $f(x_1+a_1, \ldots, x_n+a_n) = g(x_1, \ldots, x_n)$. This is a special variant of the polynomial projection problem in Algebraic ... more >>>

ISSN 1433-8092 | Imprint