Cover Image

Local Correction of Linear Functions over the Boolean Cube

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Amireddy, Prashanth, Behera, Amik Raj, Paraashar, Manaswi, Srinivasan, Srikanth, Sudan, Madhu
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

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

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
by: Amireddy, Prashanth, et al.
Published: (2025)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
by: Amireddy, Prashanth, et al.
Published: (2025)

Ideals, Macaulay Bases, and PCPs
by: Amireddy, Prashanth, et al.
Published: (2025)

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

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

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

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

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

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

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

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Algebra in Algorithmic Coding Theory
by: Sudan, Madhu
Published: (2025)

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

Improved PIR Schemes using Matching Vectors and Derivatives
by: Ghasemi, Fatemeh, et al.
Published: (2024)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
by: Błasiok, Jarosław, et al.
Published: (2026)

Sketching approximability of all finite CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

Boolean Functions with Minimal Spectral Sensitivity
by: Prūsis, Krišjānis, et al.
Published: (2024)

Special Coverings of Sets and Boolean Functions
by: Margaryan, Stepan
Published: (2024)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
by: Yamakami, Tomoyuki
Published: (2017)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
by: Mouli, Sasank
Published: (2024)

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

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

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

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

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

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

Nearest Neighbor Complexity and Boolean Circuits
by: DiCicco, Mason, et al.
Published: (2024)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
by: Michno, Katzper
Published: (2025)

Inverse Intersections for Boolean Satisfiability Problems
by: Homer, Paul W.
Published: (2025)

Boolean PCSPs through the lens of Fourier Analysis
by: Banakh, Demian, et al.
Published: (2026)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

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

Boolean functions on high-dimensional expanders
by: Dikstein, Yotam, et al.
Published: (2018)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)