Cover Image

Approximate Degree Composition for Recursive Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Sourav, Kayal, Chandrima, Mittal, Rajat, Paraashar, Manaswi, Saurabh, Nitin
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

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

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

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

Relations between monotone complexity measures based on decision tree complexity
by: Byramji, Farzan, et al.
Published: (2024)

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

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Certificate Games and Consequences for the Classical Adversary Bound
by: Chakraborty, Sourav, et al.
Published: (2022)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
by: Datta, Swarnalipa, et al.
Published: (2026)

On query complexity measures and their relations for symmetric functions
by: Mittal, Rajat, et al.
Published: (2021)

On the Approximate Non-Deterministic Degree of Total Boolean Functions
by: Pednekar, Samruddhi, et al.
Published: (2026)

A domain in $\mathbb C^4$ and its connection with $μ$-synthesis problem
by: Pal, Sourav, et al.
Published: (2026)

Hilbert Functions and Low-Degree Randomness Extractors
by: Golovnev, Alexander, et al.
Published: (2024)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
by: Yao, Penghui, et al.
Published: (2025)

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

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

The toral contractions and $Γ$-distinguished $Γ$-contractions
by: Pal, Sourav, et al.
Published: (2022)

Characterizations and models for the $C_{1,r}$ class and quantum annulus
by: Pal, Sourav, et al.
Published: (2022)

Constrained dilation and $Γ$-contractions
by: Pal, Sourav, et al.
Published: (2025)

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

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
by: Mittal, Kunal
Published: (2025)

Biased Linearity Testing in the 1% Regime
by: Khot, Subhash, et al.
Published: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
by: Uhlmann, Jeffrey
Published: (2025)

Operators associated with the hexablock
by: Pal, Sourav, et al.
Published: (2025)

Dilation on an annulus and von Neumann's inequality on certain varieties in the biball
by: Pal, Sourav, et al.
Published: (2025)

Rigidity of the structured singular value and applications
by: Pal, Sourav, et al.
Published: (2026)

Realization, interpolation, extension on the pentablock and applications to $\mathbb D^2$, $\mathbb G_2$
by: Pal, Sourav, et al.
Published: (2026)

Operators associated with the pentablock and their relations with biball and symmetrized bidisc
by: Pal, Sourav, et al.
Published: (2023)

Joint reducing subspaces and orthogonal decompositions of operators in an annulus
by: Pal, Sourav, et al.
Published: (2023)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

On the Dynamics of Bounded-Degree Automata Networks
by: Aracena, Julio, et al.
Published: (2025)

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

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

VP, VNP and Algebraic Branching Programs over Min-Plus Semirings
by: Komarath, Balagopal, et al.
Published: (2026)

Complexity of Multiple-Hamiltonicity in Graphs of Bounded Degree
by: Liu, Brian, et al.
Published: (2024)

On Factorization of Sparse Polynomials of Bounded Individual Degree
by: Chuyoon, Aminadav, et al.
Published: (2026)

The Hexablock: a domain associated with the $μ$-synthesis in $M_2(\mathbb C)$
by: Biswas, Indranil, et al.
Published: (2025)

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