Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with verification:
TR00-088 | 28th November 2000
Meena Mahajan, V Vinay

A note on the hardness of the characteristic polynomial

In this note, we consider the problem of computing the
coefficients of the characteristic polynomial of a given
matrix, and the related problem of verifying the

Santha and Tan [CC98] show that verifying the determinant
(the constant term in the characteristic polynomial) is
complete for the class C=L, ... more >>>

TR12-079 | 14th June 2012
Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer

Verifying Proofs in Constant Depth

In this paper we initiate the study of proof systems where verification of proofs proceeds by NC0 circuits. We investigate the question which languages admit proof systems in this very restricted model. Formulated alternatively, we ask which languages can be enumerated by NC0 functions. Our results show that the answer ... more >>>

TR21-144 | 13th October 2021
Leroy Chew, Friedrich Slivovsky

Towards Uniform Certification in QBF

We pioneer a new technique that allows us to prove a multitude of previously open simulations in QBF proof complexity. In particular, we show that extended QBF Frege p-simulates clausal proof systems such as IR-Calculus, IRM-Calculus, Long-Distance Q-Resolution, and Merge Resolution.
These results are obtained by taking a technique ... more >>>

ISSN 1433-8092 | Imprint