Martin Dietzfelbinger, Miroslaw Kutylowski, Rüdiger Reischuk

It was shown some years ago that the computation time for many important

Boolean functions of n arguments on concurrent-read exclusive-write

parallel random-access machines

(CREW PRAMs) of unlimited size is at least f(n) = 0.72 log n.

On the other hand, it ...
more >>>

Manindra Agrawal, Thomas Thierauf

We investigate the computational complexity of the Boolean Isomorphism problem (BI):

on input of two Boolean formulas F and G decide whether there exists a permutation of

the variables of G such that F and G become equivalent.

Our main result is a one-round interactive proof ... more >>>

Petr Savicky

For any Boolean function $f$ let $L(f)$ be its formula size

complexity in the basis $\{\land,\oplus,1\}$. For every $n$ and

every $k\le n/2$, we describe a probabilistic distribution

on formulas in the basis $\{\land,\oplus,1\}$ in some given set of

$n$ variables and of the ...
more >>>

Judy Goldsmith, Robert H. Sloan, Balázs Szörényi, György Turán

A theory, in this context, is a Boolean formula; it is

used to classify instances, or truth assignments. Theories

can model real-world phenomena, and can do so more or less

correctly.

The theory revision, or concept revision, problem is to

correct a given, roughly correct concept.

This problem is ...
more >>>

Ilias Diakonikolas, Homin Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco Servedio, Andrew Wan

We describe a general method for testing whether a function on n input variables has a concise representation. The approach combines ideas from the junta test of Fischer et al. with ideas from learning theory, and yields property testers that make poly(s/epsilon) queries (independent of n) for Boolean function classes ... more >>>

Andrej Bogdanov, Periklis Papakonstantinou, Andrew Wan

We give an explicit construction of a pseudorandom generator for read-once formulas whose inputs can be read in arbitrary order. For formulas in $n$ inputs and arbitrary gates of fan-in at most $d = O(n/\log n)$, the pseudorandom generator uses $(1 - \Omega(1))n$ bits of randomness and produces an output ... more >>>

Giorgio Ausiello, Francesco Cristiano, Luigi Laura

We investigate the complexity of the syntactic isomorphism problem of CNF Boolean Formulas (CSFI): given two CNF Boolean formulas $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ decide whether there exists a permutation of clauses, a permutation of literals and a bijection between their variables such that $\varphi(a_{1},\ldots,a_{n})$ and $\varphi(b_{1},\ldots,b_{n})$ become syntactically identical. We first ... more >>>

Siyao Guo, Ilan Komargodski

Understanding the power of negation gates is crucial to bridge the exponential gap between monotone and non-monotone computation. We focus on the model of formulas over the De Morgan basis and consider it in a negation-limited setting.

We prove that every formula that contains $t$ negation gates can be shrunk ... more >>>