Cover Image

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Datta, Swarnalipa, Ghosh, Arijit, Kayal, Chandrima, Paraashar, Manaswi, Roy, Manmatha
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms 94A05, 68Q17, 42C10, 68Q25
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

Testing Isomorphism of Boolean Functions over Finite Abelian Groups
by: Datta, Swarnalipa, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
by: Cui, Jinchuan, et al.
Published: (2022)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
by: Li, Zhangsong
Published: (2025)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Teaching and Learning under Deductive Errors
by: Telle, Jan Arne, et al.
Published: (2026)

How Does Machine Learning Manage Complexity?
by: Fortnow, Lance
Published: (2026)

On Quantum Context-Free Grammars
by: Aruja, Merina, et al.
Published: (2025)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

On the Whitney Extension-Interpolation-Alignment problem for almost isometries with small distortion in $\Bbb R^D$
by: Damelin, S. B, et al.
Published: (2014)

On Smooth Whitney Extensions of almost isometries with small distortion, Interpolation and Alignment in $\Bbb R^D$-Part 1
by: Damelin, S. B., et al.
Published: (2014)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

Adaptive Greedy Rejection Sampling
by: Flamich, Gergely, et al.
Published: (2023)

On the Whitney distortion extension problem for $C^m(\mathbb R^n)$ and $C^{\infty}(\mathbb R^n)$ and its applications to interpolation and alignment of data in $\mathbb R^n$
by: Damelin, S. B, et al.
Published: (2015)

Resolution of The Linear-Bounded Automata Question
by: Lin, Tianrong
Published: (2021)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Composable Post-Quantum Security for FADEC-Coupled Dual-Spool Turbofan Cyber-Physical Systems
by: Alpay, Faruk, et al.
Published: (2026)

Toward P vs NP: An Observer-Theoretic Separation via SPDP Rank and a ZFC-Equivalent Foundation within the N-Frame Model
by: Edwards, Darren J.
Published: (2025)

A BMO theorem for $ε$ distorted diffeomorphisms from $\mathbb R^D$ to $\mathbb R^D$ with applications to manifolds of speech and sound
by: Fefferman, C., et al.
Published: (2016)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
by: Li, Zhangsong
Published: (2026)

Binary Tree Block Encoding of Classical Matrix
by: Li, Zexian, et al.
Published: (2025)

When can forward stable algorithms be composed stably?
by: Beltrán, Carlos, et al.
Published: (2021)

Circularity and repetitiveness in non-injective DF0L systems
by: Goulet-Ouellet, Herman, et al.
Published: (2025)

Languages given by Finite Automata over the Unary Alphabet
by: Czerwiński, Wojciech, et al.
Published: (2023)

The Algorithmic Phase Transition in Correlated Spiked Models
by: Li, Zhangsong
Published: (2025)

Beyond the Existential Theory of the Reals
by: Schaefer, Marcus, et al.
Published: (2022)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Parameterized Complexity of Directed Traveling Salesman Problem
by: Blažej, Václav, et al.
Published: (2025)

A computational transition for detecting correlated stochastic block models by low-degree polynomials
by: Chen, Guanyi, et al.
Published: (2024)

Greedy Poisson Rejection Sampling
by: Flamich, Gergely
Published: (2023)

Anti-Context-Free languages
by: Cardó, Carles
Published: (2024)

The number of primitive words of unbounded exponent in the language of an HD0L-system is finite
by: Klouda, Karel, et al.
Published: (2021)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)