:: Library Catalog

Imagen de Portada

Guardado en:

Detalles Bibliográficos
Autor principal:	Margaryan, Stepan
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	https://arxiv.org/abs/2501.00008
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

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

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

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

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

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

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

Hardness of SetCover Reoptimization
por: Jansen, Klaus, et al.
Publicado: (2025)

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

Knapsack with Vertex Cover, Set Cover, and Hitting Set
por: Dey, Palash, et al.
Publicado: (2024)

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

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

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

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

On Boolean PCSPs with Polynomial Threshold Polymorphisms
por: Michno, Katzper
Publicado: (2025)

Inverse Intersections for Boolean Satisfiability Problems
por: Homer, Paul W.
Publicado: (2025)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
por: Fritsch, Timo, et al.
Publicado: (2026)

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

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

Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules
por: Hirahara, Shuichi, et al.
Publicado: (2025)

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

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

Certifiable Boolean Reasoning Is Universal
por: Li, Wenhao, et al.
Publicado: (2026)

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

Range Avoidance in Boolean Circuits via Turan-type Bounds
por: Kuntewar, Neha, et al.
Publicado: (2025)

On the Complexity of Techniques That Make Transition Systems Implementable by Boolean Nets
por: Devillers, Raymond, et al.
Publicado: (2022)

Hardness of Learning Boolean Functions from Label Proportions
por: Guruswami, Venkatesan, et al.
Publicado: (2024)

Expected Shapley-Like Scores of Boolean Functions: Complexity and Applications to Probabilistic Databases
por: Karmakar, Pratik, et al.
Publicado: (2024)

Low Sets and Closure Properties of Counting Function Classes
por: Ivanashev, Yaroslav
Publicado: (2025)

Complex Boolean Turing Machines: An Algebraic Semantic Framework for Computational Complexity
por: Zheng, Bojin, et al.
Publicado: (2026)

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

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

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
por: Fischer, Nick, et al.
Publicado: (2025)

Query complexity of Boolean functions on the middle slice of the cube
por: Gerbner, Dániel, et al.
Publicado: (2023)

Classification of Non-redundancy of Boolean Predicates of Arity 4
por: Brakensiek, Joshua, et al.
Publicado: (2026)

Model Counting for Dependency Quantified Boolean Formulas
por: Fung, Long-Hin, et al.
Publicado: (2025)

Logics with probabilistic team semantics and the Boolean negation
por: Hannula, Miika, et al.
Publicado: (2023)

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

Dual-Tape Perspective and Generator Independence: The Algebraic Foundation of Real Boolean Turing Machines
por: Zheng, Jingwen, et al.
Publicado: (2026)

Solving Quantified Boolean Formulas with Few Existential Variables
por: Eriksson, Leif, et al.
Publicado: (2024)