Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

TR22-085 | 8th June 2022
Andrzej Lingas

A Note on Lower Bounds for Monotone Multilinear Boolean Circuits

A monotone Boolean circuit is a restriction of a Boolean circuit
allowing for the use of disjunctions, conjunctions, the Boolean
constants, and the input variables. A monotone Boolean circuit is
multilinear if for any AND gate the two input functions have no
variable in common. We ... more >>>


TR22-084 | 2nd June 2022
Yanyi Liu, Rafael Pass

Characterizing Derandomization Through Hardness of Levin-Kolmogorov Complexity

A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. We consider this problem in the context of promise problems (i.e,. the $\prBPP$ v.s. $\prP$ problem) and show that for all sufficiently large constants $c$, the following ... more >>>


TR22-083 | 2nd June 2022
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

Hardness of Maximum Likelihood Learning of DPPs

Determinantal Point Processes (DPPs) are a widely used probabilistic model for negatively correlated sets. DPPs have been successfully employed in Machine Learning applications to select a diverse, yet representative subset of data. In these applications, the parameters of the DPP need to be fitted to match the data; typically, we ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint