16 citations · 17 across the 8 of their papers we have counts for
10 papers
A Hand-Checkable Proof That Two Hidden ReLU Layers Compute the Maximum of Six Numbers
Dimitrios Myrisiotis
Exactly computing the maximum function is a standard test case for studying depth in ReLU networks. Two hidden layers are known to suffice for up to twelve inputs through computer-…
Approximating the Trace Distance Between Product Quantum States
Kun He, Dimitrios Myrisiotis, Junhong Nie +1
We study the trace distance \[D_{\mathrm{tr}}(ρ,σ) =\frac12\|ρ-σ\|_1, ρ=\bigotimes_{i=1}^nρ_i,\quad σ=\bigotimes_{i=1}^nσ_i, \] when the two exponentially large states are specifie…
Algorithms and Hardness for Estimating Statistical Similarity
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We introduce and study the computational problem of determining statistical similarity between probability distributions. For distributions and over a finite sample space,…
Computational Explorations of Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We investigate some previously unexplored (or underexplored) computational aspects of total variation (TV) distance. First, we give a simple deterministic polynomial-time algorithm…
Efficient, Low-Regret, Online Reinforcement Learning for Linear MDPs
Philips George John, Arnab Bhattacharyya, Silviu Maniu +2
Reinforcement learning algorithms are usually stated without theoretical guarantees regarding their performance. Recently, Jin, Yang, Wang, and Jordan (COLT 2020) showed a polynomi…
Learnability of Parameter-Bounded Bayes Nets
Arnab Bhattacharyya, Davin Choo, Sutanu Gayen +1
Bayes nets are extensively used in practice to efficiently represent joint probability distributions over a set of random variables and capture dependency relations. In a seminal p…
Total Variation Distance for Product Distributions is -Complete
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
We show that computing the total variation distance between two product distributions is -complete. This is in stark contrast with other distance measures such as Kul…
Total Variation Distance Meets Probabilistic Inference
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-prese…
On Approximating Total Variation Distance
Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel +3
Total variation distance (TV distance) is a fundamental notion of distance between probability distributions. In this work, we introduce and study the problem of computing the TV d…
Algorithms and Lower Bounds for de Morgan Formulas of Low-Communication Leaf Gates
Valentine Kabanets, Sajin Koroth, Zhenjian Lu +2
The class consists of Boolean functions computable by size- de Morgan formulas whose leaves are any Boolean functions from a class .…