Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Karl Wimmer:

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

TR20-062 | 29th April 2020
Clement Canonne, Karl Wimmer

Testing Data Binnings

Motivated by the question of data quantization and "binning," we revisit the problem of identity testing of discrete probability distributions. Identity testing (a.k.a. one-sample testing), a fundamental and by now well-understood problem in distribution testing, asks, given a reference distribution (model) $\mathbf{q}$ and samples from an unknown distribution $\mathbf{p}$, both ... more >>>

TR17-088 | 10th May 2017
Elena Grigorescu, Akash Kumar, Karl Wimmer

K-Monotonicity is Not Testable on the Hypercube

Revisions: 1

We continue the study of $k$-monotone Boolean functions in the property testing model, initiated by Canonne et al. (ITCS 2017). A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it alternates between $0$ and $1$ at most $k$ times on every ascending chain. Such functions represent a natural generalization ... more >>>

TR16-136 | 31st August 2016
Clement Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer

Testing k-Monotonicity

Revisions: 1

A Boolean $k$-monotone function defined over a finite poset domain ${\cal D}$ alternates between the values $0$ and $1$ at most $k$ times on any ascending chain in ${\cal D}$. Therefore, $k$-monotone functions are natural generalizations of the classical monotone functions, which are the $1$-monotone functions.

Motivated by the ... more >>>

TR15-030 | 6th March 2015
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie

${\mathrm{AC}^{0} \circ \mathrm{MOD}_2}$ lower bounds for the Boolean Inner Product

Revisions: 1

$\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuits are $\mathrm{AC}^{0}$ circuits augmented with a layer of parity gates just above the input layer. We study the $\mathrm{AC}^{0} \circ \mathrm{MOD}_2$ circuit lower bound for computing the Boolean Inner Product functions. Recent works by Servedio and Viola (ECCC TR12-144) and Akavia et al. (ITCS 2014) have ... more >>>

TR13-090 | 18th June 2013
Elena Grigorescu, Karl Wimmer, Ning Xie

Tight Lower Bounds for Testing Linear Isomorphism

We study lower bounds for testing membership in families of linear/affine-invariant Boolean functions over the hypercube. A family of functions $P\subseteq \{\{0,1\}^n \rightarrow \{0,1\}\}$ is linear/affine invariant if for any $f\in P$, it is the case that $f\circ L\in P$ for any linear/affine transformation $L$ of the domain. Motivated by ... more >>>

ISSN 1433-8092 | Imprint