All reports by Author Erfan Khaniki:

__
TR22-023
| 19th February 2022
__

Erfan Khaniki#### Nisan--Wigderson generators in Proof Complexity: New lower bounds

__
TR20-034
| 12th March 2020
__

Erfan Khaniki#### On Proof complexity of Resolution over Polynomial Calculus

Revisions: 3

Erfan Khaniki

A map $g:\{0,1\}^n\to\{0,1\}^m$ ($m>n$) is a hard proof complexity generator for a proof system $P$ iff for every string $b\in\{0,1\}^m\setminus Rng(g)$, formula $\tau_b(g)$ naturally expressing $b\not\in Rng(g)$ requires superpolynomial size $P$-proofs. One of the well-studied maps in the theory of proof complexity generators is Nisan--Wigderson generator. Razborov (Annals of Mathematics ... more >>>

Erfan Khaniki

The refutation system ${Res}_R({PC}_d)$ is a natural extension of resolution refutation system such that it operates with disjunctions of degree $d$ polynomials over ring $R$ with boolean variables. For $d=1$, this system is called ${Res}_R({lin})$. Based on properties of $R$, ${Res}_R({lin})$ systems can be too strong to prove lower ... more >>>