Mladen Kovačević

Mladen Kovačević

Let $M$ be a matroid on a finite ground set $E$, and suppose that the automorphism group of $M$ acts transitively on $E$. We show the following: if $X_1,\ldots,X_K$ are sampled independently from a distribution $p$ on $E$, then the probability that the samples are distinct and that $\{X_1,\ldots,X_K\}$ is an independent set in $M$ is quasi-concave in $p$ and maximized when $p$ is uniform. As a corollary, for a random $K\times N$ matrix over a finite field whose rows are sampled independently from an arbitrary distribution on nonzero projective row classes, the uniform distribution on projective space maximizes the probability of full row rank. In this particular case we also establish the uniqueness of the maximizer and global quadratic stability, while a simple example illustrates that uniqueness and stability need not hold for arbitrary transitive matroids.

Mladen Kovačević

The classical problem of maximizing the Shannon entropy of a sum of independent random variables supported on a finite alphabet is considered and settled in the ternary case. Namely, the following theorem is established: if \(X_1,\ldots,X_n\) are independent random variables taking values in \(\{0,1,2\}\), then the entropy of \(S_n=X_1+\cdots+X_n\) is maximized when \(X_1,\ldots,X_{n-1}\) are uniform on \(\{0,2\}\) and the probability mass function of \(X_n\) is given by \(\Prob(X_n=0) = \Prob(X_n=2) = w/2\), \(\Prob(X_n=1) = 1-w\), where \(w = \big(1 + 2^{-H(B_n)+H(B_{n-1})}\big)^{-1}\) and \(B_m\sim \Bin(m,1/2)\). The statement can be seen as an extension to ternary alphabets of the Shepp--Olkin--Mateev theorem. The proof uses the Hermite--Biehler theorem, Newton's inequalities, and Yu's maximum-entropy theorem for ultra-log-concave distributions.

Patrik Velčický, Jakub Breier, Mladen Kovačević et al.

Fault injection attacks are a potent threat against embedded implementations of neural network models. Several attack vectors have been proposed, such as misclassification, model extraction, and trojan/backdoor planting. Most of these attacks work by flipping bits in the memory where quantized model parameters are stored. In this paper, we introduce an encoding-based protection method against bit-flip attacks on neural networks, titled DeepNcode. We experimentally evaluate our proposal with several publicly available models and datasets, by using state-of-the-art bit-flip attacks: BFA, T-BFA, and TA-LBF. Our results show an increase in protection margin of up to $7.6\times$ for $4-$bit and $12.4\times$ for $8-$bit quantized networks. Memory overheads start at $50\%$ of the original network size, while the time overheads are negligible. Moreover, DeepNcode does not require retraining and does not change the original accuracy of the model.