Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with lower bonds:
TR97-021 | 16th May 1997
Farid Ablayev

Randomization and nondeterminsm are incomparable for ordered read-once branching programs

In the manuscript F. Ablayev and M. Karpinski, On the power of
randomized branching programs (generalization of ICALP'96 paper
results for the case of pure boolean function, available at
http://www.ksu.ru/~ablayev) we exhibited a simple boolean functions
$f_n$ in $n$ variables such that:

1) $f_{n}$ can be computed ... more >>>

TR23-129 | 21st August 2023
Sravanthi Chede, Leroy Chew, Balesh Kumar, Anil Shukla

Understanding Nullstellensatz for QBFs

QBF proof systems are routinely adapted from propositional logic along with adjustments for the new quantifications. Existing are two main successful frameworks, the reduction and expansion frameworks, inspired by QCDCL [Zhang et al. ICCAD.'2002] and CEGAR solving [Janota et al. Artif. Intell.'2016] respectively. However, the reduction framework, while immensely useful ... more >>>

ISSN 1433-8092 | Imprint