Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

RSS-FeedNext next

TR23-147 | 27th September 2023
Vikraman Arvind, Abhranil Chatterjee, Partha Mukhopadhyay

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time

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

TR23-146 | 27th September 2023
Oded Goldreich, Laliv Tauber

On Testing Isomorphism to a Fixed Graph in the Bounded-Degree Graph Model

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

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

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 next

ISSN 1433-8092 | Imprint