Cover Image

No Constant-Cost Protocol for Point--Line Incidence

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Göös, Mika, Harms, Nathaniel, Richter, Florian K., Sofronova, Anastasia
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity 68Q11, 68Q25, 11B30
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Sign-Rank of $k$-Hamming Distance is Constant
by: Göös, Mika, et al.
Published: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

A weak regularity lemma for polynomials
by: Moshkovitz, Guy, et al.
Published: (2025)

On the Characteristic Polynomial of Linearized Polynomials
by: Bastioni, Luca, et al.
Published: (2025)

Fast Algorithms for the Computation of the Minimum Distance of a Random Linear Code
by: Hernando, Fernando, et al.
Published: (2016)

Implementing Basic Arithmetic in $\mathbb{F}_p$ via $\mathbb{F}_2$, and Its Application for Computing the Hamming Distance of Linear Codes
by: Hernando, Fernando, et al.
Published: (2026)

Certified Finite-State Induction for a Perturbed Hofstadter Recursion
by: Mantovanelli, Marco
Published: (2026)

The Complexity of Iterated Reversible Computation
by: Eppstein, David
Published: (2021)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Shrinkage under Random Projections, and Cubic Formula Lower Bounds for $\mathsf{AC}^0$
by: Filmus, Yuval, et al.
Published: (2020)

Compression with wildcards: All models of a Boolean 2-CNF
by: Wild, Marcel
Published: (2012)

ASP-Completeness of Hamiltonicity in Grid Graphs, with Applications to Loop Puzzles
by: MIT Hardness Group, et al.
Published: (2024)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

A Study of NP-Completeness and Undecidable Word Problems in Semigroups
by: Abdullah, Duaa, et al.
Published: (2025)

Red-Blue Pebbling with Multiple Processors: Time, Communication and Memory Trade-offs
by: Böhnlein, Toni, et al.
Published: (2024)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
by: Avila, Tatiana Rocha, et al.
Published: (2026)

Cluster Vertex Deletion Problems on Cubic Graphs
by: Rusu, Irena
Published: (2025)

Bounded Distance Decoding for Random Lattices
by: Gao, Shuhong
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

CircuitBuilder: From Polynomials to Circuits via Reinforcement Learning
by: Zhang, Weikun K., et al.
Published: (2026)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

On weighted graph separation problems and flow-augmentation
by: Kim, Eun Jung, et al.
Published: (2022)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Classically Time-Controlled Quantum Automata: Definition and Properties
by: Díaz-Caro, Alejandro, et al.
Published: (2018)

Low communication protocols for fair allocation of indivisible goods
by: Feige, Uriel
Published: (2024)

The Separation of $NP$ and $PSPACE$
by: Lin, Tianrong
Published: (2021)

Unifying lower bounds for algebraic machines, semantically
by: Seiller, Thomas, et al.
Published: (2018)

How Does Machine Learning Manage Complexity?
by: Fortnow, Lance
Published: (2026)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)

Curved Boolean Logic: A Contextual Generalization of Propositional Logic with Algorithmic Consequences
by: von Liechtenstein, Maximilian R. P.
Published: (2025)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
by: Alpay, Faruk, et al.
Published: (2026)

On the Low Weight Polynomial Multiple Problem
by: Ţiplea, Ferucio Laurenţiu, et al.
Published: (2024)

The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Algorithmic Barriers to Detecting and Repairing Structural Overspecification in Adaptive Data-Structure Selection
by: Alpay, Faruk, et al.
Published: (2026)

Recent Advances in Debordering Methods
by: Dutta, Pranjal, et al.
Published: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

All Kolmogorov complexity functions are optimal, but are some more optimal?
by: Bauwens, Bruno, et al.
Published: (2025)

Increasing-decreasing patterns in the iteration of an arithmetic function
by: Nathanson, Melvyn B.
Published: (2022)