Cover Image

Structure of sparse Boolean functions over Abelian groups, and its application to testing

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Sourav, Datta, Swarnalipa, Dutta, Pranjal, Ghosh, Arijit, Sanyal, Swagato
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity 68 F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
by: Dutta, Pranjal, et al.
Published: (2023)

Fixed-parameter debordering of Waring rank
by: Dutta, Pranjal, et al.
Published: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
by: Conneryd, Jonas, et al.
Published: (2025)

Geometric complexity theory for product-plus-power
by: Dutta, Pranjal, et al.
Published: (2022)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
by: Bodnar, Levente
Published: (2024)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
by: Rossman, Benjamin
Published: (2024)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Algebraic metacomplexity and representation theory
by: Berg, Maxim van den, et al.
Published: (2024)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Complexity Classes Arising from Circuits over Finite Algebraic Structures
by: Kawałek, Piotr, et al.
Published: (2026)

Quantum Sabotage Complexity
by: Cornelissen, Arjan, et al.
Published: (2024)

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

On the computational complexity of Data Flow Analysis
by: Sood, Gaurav, et al.
Published: (2013)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
by: Hakoniemi, Tuomas, et al.
Published: (2024)

Quantum algorithms through graph composition
by: Cornelissen, Arjan
Published: (2025)

Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)

NP-hardness of p-adic linear regression
by: Baker, Gregory D.
Published: (2026)

Failure of the strong feasible disjunction property
by: Krajicek, Jan
Published: (2026)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

I/O complexity and pebble games with partial computations
by: Sobczyk, Aleksandros
Published: (2024)

Quoridor is PSPACE-Complete
by: Drop, Marius, et al.
Published: (2026)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

Nonuniform Deterministic Finite Automata over finite algebraic structures
by: Idziak, Paweł M., et al.
Published: (2025)

Stochastic well-structured transition systems
by: Aspnes, James
Published: (2025)

Functional Closure Properties of Finite $\mathbb{N}$-weighted Automata
by: Dörfler, Julian, et al.
Published: (2024)