research
∙
04/28/2023
Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
We develop the theory of cryptographic nondeterministic-secure pseudoran...
share
research
∙
05/15/2022
Simple Hard Instances for Low-Depth Algebraic Proofs
We prove super-polynomial lower bounds on the size of propositional proo...
research
∙
05/16/2021
First-Order Reasoning and Efficient Semi-Algebraic Proofs
Semi-algebraic proof systems such as sum-of-squares (SoS) have attracted...
research
∙
11/15/2019
Semi-Algebraic Proofs, IPS Lower Bounds and the τ-Conjecture: Can a Natural Number be Negative?
We introduce the binary value principle which is a simple subset-sum ins...
research
∙
11/10/2018
Uniform, Integral and Feasible Proofs for the Determinant Identities
Aiming to provide weak as possible axiomatic assumptions in which one ca...
research
∙
06/25/2018