Next

__
TR23-147
| 27th September 2023
__

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay#### Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

__
TR23-146
| 27th September 2023
__

Oded Goldreich, Laliv Tauber#### On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

__
TR23-145
| 20th September 2023
__

Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran#### Total Variation Distance Estimation Is as Easy as Probabilistic Inference

Next

Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Rational Identity Testing (RIT) is the decision problem of determining whether or not a given noncommutative rational formula computes zero in the free skew field. It admits a deterministic polynomial-time white-box algorithm [Garg et al., 2016; Ivanyos et al., 2018; Hamada and Hirai, 2021], and a randomized polynomial-time black-box algorithm ... more >>>

Oded Goldreich, Laliv Tauber

We consider the problem of testing isomorphism to a fixed graph in the bounded-degree graph model. Our main result is that, for almost all $d$-regular $n$-vertex graphs $H$,

testing isomorphism to $H$ can be done using $\tildeO({\sqrt n})$ queries.

This result is shown to be optimal (up to ...
more >>>

Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, Dimitrios Myrisiotis, A. Pavan, N. V. Vinodchandran

In this paper, we establish a novel connection between total variation (TV) distance estimation and probabilistic inference. In particular, we present an efficient, structure-preserving reduction from relative approximation of TV distance to probabilistic inference over directed graphical models. This reduction leads to a fully polynomial randomized approximation scheme (FPRAS) for ... more >>>

Next