Image de couverture de livre

Parity Tests with Ties

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Kupfer, Ron
Format:	Preprint
Publié:	2026
Sujets:	Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
par: Chew, Leroy, et autres
Publié: (2024)

Exponential Separation Between Powers of Regular and General Resolution Over Parities
par: Bhattacharya, Sreejata Kishor, et autres
Publié: (2024)

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
par: Byramji, Farzan, et autres
Publié: (2025)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
par: Dalirrooyfard, Mina, et autres
Publié: (2025)

Query complexity lower bounds for local list-decoding and hard-core predicates (even for small rate and huge lists)
par: Ron-Zewi, Noga, et autres
Publié: (2024)

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
par: Gretta, Lucas, et autres
Publié: (2026)

Distribution-Free Proofs of Proximity
par: Aaronson, Hugo, et autres
Publié: (2023)

Advances in List Decoding of Polynomial Codes
par: Kumar, Mrinal, et autres
Publié: (2026)

New Direct Sum Tests
par: Westover, Alek, et autres
Publié: (2024)

Biased Linearity Testing in the 1% Regime
par: Khot, Subhash, et autres
Publié: (2025)

Low-Degree Testing Over Grids
par: Amireddy, Prashanth, et autres
Publié: (2023)

On Matrix Multiplication and Polynomial Identity Testing
par: Andrews, Robert
Publié: (2022)

Direct Sums for Parity Decision Trees
par: Besselman, Tyler, et autres
Publié: (2024)

Optimization of a Quantum Subset Sum Oracle
par: Benoit, Angelo, et autres
Publié: (2024)

Isomorphism Testing of Rooted Trees in Linear Time
par: Lindeberg, Anna
Publié: (2024)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
par: Ramya, C., et autres
Publié: (2025)

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
par: Bhattacharjee, Sutanay, et autres
Publié: (2026)

Efficient Polynomial Identity Testing Over Nonassociative Algebras
par: Mukhopadhyay, Partha, et autres
Publié: (2025)

Characterizing Direct Product Testing via Coboundary Expansion
par: Bafna, Mitali, et autres
Publié: (2023)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
par: Datta, Swarnalipa, et autres
Publié: (2023)

Polynomial Identity Testing and Reconstruction for Depth-4 Powering Circuits of High Degree
par: Shpilka, Amir, et autres
Publié: (2026)

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
par: Kopparty, Swastik, et autres
Publié: (2023)

Communication Separations for Truthful Auctions: Breaking the Two-Player Barrier
par: Ron, Shiri, et autres
Publié: (2024)

Interactive Proofs For Distribution Testing With Conditional Oracles
par: Biswas, Ari, et autres
Publié: (2025)

Direct Product Primality Testing of Graphs is GI-hard
par: Calderoni, Luca, et autres
Publié: (2020)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
par: Abboud, Amir, et autres
Publié: (2026)

Graphical Tests of Causality
par: Baumeler, Ämin, et autres
Publié: (2025)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
par: Garg, Abhibhav, et autres
Publié: (2025)

Testing for Renamability to Classes of Clause Sets
par: Brandl, Albert, et autres
Publié: (2025)

Property Testing in Bounded Degree Hypergraphs
par: Aaronson, Hugo, et autres
Publié: (2025)

LDPC Codes Achieve List Decoding Capacity
par: Mosheiff, Jonathan, et autres
Publié: (2019)

Quantum Algorithms for Approximate Graph Isomorphism Testing
par: Kulkarni, Prateek P.
Publié: (2026)

Relaxed Local Correctability from Local Testing
par: Kumar, Vinayak M., et autres
Publié: (2023)

Revealing POMDPs: Qualitative and Quantitative Analysis for Parity Objectives
par: Asadi, Ali, et autres
Publié: (2025)

Lower Bounds for Unitary Property Testing with Proofs and Advice
par: Weggemans, Jordi
Publié: (2024)

Coherence in Property Testing: Quantum-Classical Collapses and Separations
par: Jeronimo, Fernando Granha, et autres
Publié: (2024)

On Optimal Testing of Linearity
par: Arora, Vipul, et autres
Publié: (2024)

Local Test for Unitarily Invariant Properties of Bipartite Quantum States
par: Chen, Kean, et autres
Publié: (2024)

Identity Testing for Radical Expressions
par: Balaji, Nikhil, et autres
Publié: (2022)

Testing Properties of Edge Distributions
par: Fei, Yumou
Publié: (2026)