Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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