Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > FORMULA LOWER BOUND:
Reports tagged with formula lower bound:
TR16-035 | 11th March 2016
Irit Dinur, Or Meir

#### Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions \$f\circ g\$. They showed that this conjecture, ... more >>>

TR16-179 | 15th November 2016
Avishay Tal

#### Computing Requires Larger Formulas than Approximating

A de Morgan formula over Boolean variables \$x_1, \ldots, x_n\$ is a binary tree whose internal nodes are marked with AND or OR gates and whose leaves are marked with variables or their negation. We define the size of the formula as the number of leaves in it. Proving that ... more >>>

ISSN 1433-8092 | Imprint