Next

__
TR21-054
| 14th April 2021
__

James Cook, Ian Mertz#### Encodings and the Tree Evaluation Problem

__
TR21-053
| 13th April 2021
__

Jan Krajicek#### Information in propositional proofs and algorithmic proof search

__
TR21-052
| 12th April 2021
__

Benny Applebaum, Oded Nir#### Upslices, Downslices, and Secret-Sharing with Complexity of $1.5^n$

Next

James Cook, Ian Mertz

We show that the Tree Evaluation Problem with alphabet size $k$ and height $h$ can be solved by branching programs of size $k^{O(h/\log h)} + 2^{O(h)}$. This answers a longstanding challenge of Cook et al. (2009) and gives the first general upper bound since the problem's inception.

more >>>Jan Krajicek

We study from the proof complexity perspective the (informal) proof search problem:

Is there an optimal way to search for propositional proofs?

We note that for any fixed proof system there exists a time-optimal proof search algorithm. Using classical proof complexity results about reflection principles we prove that a time-optimal ...
more >>>

Benny Applebaum, Oded Nir

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$.

The collection of authorized/unauthorized sets can be captured by a monotone function $f:\{0,1\}^n\rightarrow \{0,1\}$.

more >>>

Next