Cover Image

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Pavlov, Gorgi
Format:	Preprint
Published:	2026
Subjects:	Machine Learning Computational Complexity Discrete Mathematics Combinatorics F.2.2; G.2.1; F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
by: Anand, Emile
Published: (2025)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
by: Burke, Kyle, et al.
Published: (2025)

New Results on Edge-coloring and Total-coloring of Split Graphs
by: Couto, Fernanda, et al.
Published: (2023)

On the Complexity of Problems on Graphs Defined on Groups
by: Das, Bireswar, et al.
Published: (2025)

On Sampling Lower Bounds for Polynomials
by: Khodabandeh, Mohammad Mahdi, et al.
Published: (2026)

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
by: Prolubnikov, Alexander
Published: (2015)

Optimal covering of rectangular grid graphs with tours of constrained length
by: Bereg, Sergey, et al.
Published: (2025)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

On Minimum Maximal Distance-k Matchings
by: Kartynnik, Yury, et al.
Published: (2016)

Enumeration of Polyominoes up to Size N=59
by: Shirakawa, Toshihiro
Published: (2025)

Slow Convergence of Ising and Spin Glass Models with Well-Separated Frustrated Vertices
by: Gillman, David, et al.
Published: (2026)

An efficient algorithm to compute the minimum free energy of interacting nucleic acid strands
by: Shalaby, Ahmed, et al.
Published: (2024)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
by: Chen, Yijia, et al.
Published: (2023)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)

Output-sensitive Complexity of Multi-Objective Integer Network Flow Problems
by: Könen, David, et al.
Published: (2023)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
by: Burke, Kyle, et al.
Published: (2024)

A Permutation Avoidance Game with Reverse Replies and Monotone Traps
by: Ulfarsson, Henning
Published: (2026)

About almost covering subsets of the hypercube
by: Ghosh, Arijit, et al.
Published: (2024)

Quantitative Edge Eigenvector Universality for Random Regular Graphs: Berry-Esseen Bounds with Explicit Constants
by: Nagel, Leonhard
Published: (2025)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
by: Zhong, Xianghui
Published: (2018)

Improving the Crossing Lemma by Characterizing Dense 2-Planar and 3-Planar Graphs
by: Büngener, Aaron, et al.
Published: (2024)

Breaking the Symmetries of Amenable Graphs
by: Cheng, Christine T.
Published: (2025)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

Efficient Uniform Sampling of Surjections via their Profiles
by: Carayol, Arnaud, et al.
Published: (2026)

Fair Division Among Couples and Small Groups
by: Gölz, Paul, et al.
Published: (2025)

Battle Sheep is PSPACE-complete
by: Burke, Kyle, et al.
Published: (2025)

On The Roots of Independence Polynomial: Quantifying The Gap
by: Prakash, Om, et al.
Published: (2025)

Graph Parameters, Universal Obstructions, and WQO
by: Paul, Christophe, et al.
Published: (2023)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

Block-weighted random graphs: planar and beyond
by: Kang, Mihyun, et al.
Published: (2026)

Asymptotic Transfer in Critical Recursive Composition Schemes
by: Drmota, Michael, et al.
Published: (2026)

Patrolling Grids with a Bit of Memory
by: Amir, Michael, et al.
Published: (2023)

Notes on CSPs and Polymorphisms
by: Brady, Zarathustra
Published: (2022)