Cover Image

On the Approximate Non-Deterministic Degree of Total Boolean Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Pednekar, Samruddhi, Podder, Supartha
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity Quantum Physics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

New Lower-bounds for Quantum Computation with Non-Collapsing Measurements
by: Miloschewsky, David, et al.
Published: (2024)

Modifications of Quantum Computation and Adaptive Queries to PP
by: Miloschewsky, David, et al.
Published: (2025)

En Route to a Standard QMA1 vs. QCMA Oracle Separation
by: Miloschewsky, David, et al.
Published: (2026)

The Role of piracy in quantum proofs
by: Broadbent, Anne, et al.
Published: (2024)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Approximate Degrees of Multisymmetric Properties with Application to Quantum Claw Detection
by: Tani, Seiichiro
Published: (2024)

Following Forrelation -- Quantum Algorithms in Exploring Boolean Functions' Spectra
by: Dutta, Suman, et al.
Published: (2021)

Approximation algorithms for noncommutative CSPs
by: Culf, Eric, et al.
Published: (2023)

The Communication Complexity of Approximating Matrix Rank
by: Sherstov, Alexander A., et al.
Published: (2024)

Quantum Algorithms for Approximate Graph Isomorphism Testing
by: Kulkarni, Prateek P.
Published: (2026)

Sampling Frequency Thresholds for Quantum Advantage of Quantum Approximate Optimization Algorithm
by: Lykov, Danylo, et al.
Published: (2022)

Quadratic Lower bounds on the Approximate Stabilizer Rank: A Probabilistic Approach
by: Mehraban, Saeed, et al.
Published: (2023)

From Promises to Totality: A Framework for Ruling Out Quantum Speedups
by: Huffstutler, Thomas, et al.
Published: (2026)

Constant-depth circuits for Boolean functions and quantum memory devices using multi-qubit gates
by: Allcock, Jonathan, et al.
Published: (2023)

Logarithmic Depth Decomposition of Approximate Multi-Controlled Single-Qubit Gates Without Ancilla Qubits
by: Silva, Jefferson D. S., et al.
Published: (2025)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Approximating the quantum value of an LCS game is RE-hard
by: Taller, Aviv, et al.
Published: (2025)

The Power of Unentangled Quantum Proofs with Non-negative Amplitudes
by: Jeronimo, Fernando Granha, et al.
Published: (2024)

Computational Complexity and Simulability of Non-Hermitian Quantum Dynamics
by: Barch, Brian, et al.
Published: (2025)

Non-signalling parallel repetition using de Finetti reductions
by: Arnon, Rotem, et al.
Published: (2014)

Are uncloneable proof and advice states strictly necessary?
by: Chatterjee, Rohit, et al.
Published: (2024)

Monte Carlo to Las Vegas for Recursively Composed Functions
by: Al-Dhalaan, Bandar, et al.
Published: (2026)

Quantum and Classical Communication Complexity of Permutation-Invariant Functions
by: Guan, Ziyi, et al.
Published: (2023)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

Quantum Property Testing for Bounded-Degree Directed Graphs
by: Peng, Pan, et al.
Published: (2026)

When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits
by: Upreti, Varun, et al.
Published: (2025)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
by: Yamakami, Tomoyuki
Published: (2023)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Exact versus Approximate Representations of Boolean Functions in the De Morgan Basis
by: Chattopadhyay, Arkadev, et al.
Published: (2025)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
by: Chang, Fan, et al.
Published: (2025)

Fermionic Gaussian Testing and Non-Gaussian Measures via Convolution
by: Lyu, Xingjian, et al.
Published: (2024)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
by: Zhang, Yifan F., et al.
Published: (2025)

Quantum-Computable One-Way Functions without One-Way Functions
by: Kretschmer, William, et al.
Published: (2024)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
by: Chia, Nai-Hui, et al.
Published: (2025)

Quantum Cryptography and Hardness of Non-Collapsing Measurements
by: Morimae, Tomoyuki, et al.
Published: (2025)

Refuting the Direct Sum Conjecture for Total Functions in Deterministic Communication Complexity
by: Mackenzie, Simon, et al.
Published: (2024)

Quantum Advantage from One-Way Functions
by: Morimae, Tomoyuki, et al.
Published: (2023)

Classical Algorithms for Constant Approximation of the Ground State Energy of Local Hamiltonians
by: Gall, François Le
Published: (2024)

On the (Classical and Quantum) Fine-Grained Complexity of Approximate CVP and Max-Cut
by: Huang, Jeremy Ahrens, et al.
Published: (2024)

Quantum Fast Implementation of Functional Bootstrapping and Private Information Retrieval
by: Ma, Guangsheng, et al.
Published: (2024)