Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > REAL COMPUTATION:
Reports tagged with real computation:
TR19-036 | 5th March 2019
Pavel Hrubes

#### On the complexity of computing a random Boolean function over the reals

Revisions: 1

We say that a first-order formula $A(x_1,\dots,x_n)$ over $\mathbb{R}$ defines a Boolean function $f:\{0,1\}^n\rightarrow\{0,1\}$, if for every $x_1,\dots,x_n\in\{0,1\}$, $A(x_1,\dots,x_n)$ is true iff $f(x_1,\dots,x_n)=1$. We show that:

(i) every $f$ can be defined by a formula of size $O(n)$,
(ii) if $A$ is required to have at most $k\geq 1$ ... more >>>

TR22-006 | 12th January 2022
Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi

#### Secret Sharing, Slice Formulas, and Monotone Real Circuits

A secret-sharing scheme allows to distribute a secret $s$ among $n$ parties such that only some predefined authorized'' sets of parties can reconstruct the secret, and all other unauthorized'' sets learn nothing about $s$. For over 30 years, it was known that any (monotone) collection of authorized sets can be ... more >>>

ISSN 1433-8092 | Imprint