Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with average-case lower bound:
TR15-099 | 12th June 2015
Ruiwen Chen

Satisfiability Algorithms and Lower Bounds for Boolean Formulas over Finite Bases

We give a \#SAT algorithm for boolean formulas over arbitrary finite bases. Let $B_k$ be the basis composed of all boolean functions on at most $k$ inputs. For $B_k$-formulas on $n$ inputs of size $cn$, our algorithm runs in time $2^{n(1-\delta_{c,k})}$ for $\delta_{c,k} = c^{-O(c^2k2^k)}$. We also show the average-case ... more >>>

TR22-153 | 8th November 2022
Eshan Chattopadhyay, Jyun-Jie Liao

Hardness against Linear Branching Programs and More

In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once
branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is
a branching program where each node is allowed to make $\mathbb{F}_2$-linear queries, and are read-once in the ... more >>>

ISSN 1433-8092 | Imprint