28 citations · 112 across the 18 of their papers we have counts for
Showing 2016Show all
3 papers · 1 filter
cs.CC2016★ 2 cited
On Probabilistic Checking in Perfect Zero Knowledge
Eli Ben-Sasson, Alessandro Chiesa, Michael A. Forbes +3
We present the first constructions of single-prover proof systems that achieve perfect zero knowledge (PZK) for languages beyond NP, under no intractability assumptions: 1. The com…
cs.CC2016★ 9 cited
Proof Complexity Lower Bounds from Algebraic Circuit Complexity
Michael A. Forbes, Amir Shpilka, Iddo Tzameret +1
We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits c…
cs.CC2016
Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity
Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi
We say that a circuit over a field functionally computes an -variate polynomial if for every we have that . This is in contrast to syn…