Cover Image

The Rank-Ramsey Problem and the Log-Rank Conjecture

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Beniamini, Gal, Linial, Nati, Shraibman, Adi
Format:	Preprint
Published:	2024
Subjects:	Combinatorics Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Log-Rank Conjecture: New Equivalent Formulations
by: Hambardzumyan, Lianna, et al.
Published: (2025)

A Study of the Binary and Boolean Rank of Matrices with Small Constant Real Rank
by: Parnas, Michal, et al.
Published: (2025)

Spiky Rank and Its Applications to Rigidity and Circuits
by: Hambardzumyan, Lianna, et al.
Published: (2026)

The Fine-Grained Complexity of Graph Homomorphism Problems: Towards the Okrasa and Rzążewski Conjecture
by: Baril, Ambroise, et al.
Published: (2024)

On the Keevash-Knox-Mycroft Conjecture
by: Gan, Luyining, et al.
Published: (2022)

Reinforced Generation of Combinatorial Structures: Ramsey Numbers
by: Nagda, Ansh, et al.
Published: (2026)

Parameterised Holant Problems
by: Aivasiliotis, Panagiotis, et al.
Published: (2024)

Hardness of Hypergraph Edge Modification Problems
by: Gishboliner, Lior, et al.
Published: (2025)

Real Stability and Log Concavity are coNP-Hard
by: Chin, Tracy
Published: (2024)

On Degeneracy in the P-Matroid Oriented Matroid Complementarity Problem
by: Borzechowski, Michaela, et al.
Published: (2023)

The Complexity Classes of Hamming Distance Recoverable Robust Problems
by: Grüne, Christoph
Published: (2022)

King Chasing Problem in Chinese Chess is NP-hard
by: Li, Chao, et al.
Published: (2026)

Sparse High Dimensional Expanders via Local Lifts
by: Yaacov, Inbar Ben, et al.
Published: (2024)

Metric Approximations of Consistent Path Systems
by: Cizma, Daniel, et al.
Published: (2026)

Time to Cycle
by: Lavee, Nir, et al.
Published: (2025)

On the Number of Path Systems
by: Cizma, Daniel, et al.
Published: (2025)

Every Poset has a Large Cut
by: Linial, Nati, et al.
Published: (2025)

On the weight distribution of random binary linear codes
by: Linial, Nati, et al.
Published: (2018)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
by: Leake, Jonathan, et al.
Published: (2025)

The Subgraph Isomorphism Problem for Port Graphs and Quantum Circuits
by: Mondada, Luca, et al.
Published: (2023)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
by: Aravind, Abhiram, et al.
Published: (2026)

Strong Inapproximability for a Promise Rank Problem
by: Guruswami, Venkatesan, et al.
Published: (2026)

A SAT Solver and Computer Algebra Attack on the Minimum Kochen-Specker Problem
by: Li, Zhengyu, et al.
Published: (2023)

Kernelization Complexity of Solution Discovery Problems
by: Grobler, Mario, et al.
Published: (2024)

Low-Degree Polynomials Are Good Extractors
by: Alrabiah, Omar, et al.
Published: (2024)

Improved Lower Bounds for all Odd-Query Locally Decodable Codes
by: Basu, Arpon, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VI
by: Bhangale, Amey, et al.
Published: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
by: Bhangale, Amey, et al.
Published: (2024)

Small Even Covers, Locally Decodable Codes and Restricted Subgraphs of Edge-Colored Kikuchi Graphs
by: Hsieh, Jun-Ting, et al.
Published: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

Constant Degree Direct Product Testers with Small Soundness
by: Bafna, Mitali, et al.
Published: (2024)

A criterion for Andrásfai--Erdős--Sós type theorems and applications
by: Hou, Jianfeng, et al.
Published: (2024)

Bisection Width, Discrepancy, and Eigenvalues of Hypergraphs
by: Räty, Eero, et al.
Published: (2024)

Corners in Quasirandom Groups via Sparse Mixing
by: Jaber, Michael, et al.
Published: (2024)

A combinatorial view of Holant problems on higher domains
by: Liu, Yin
Published: (2024)

Reasonable Bounds for Combinatorial Lines of Length Three
by: Bhangale, Amey, et al.
Published: (2024)

Boosting uniformity in quasirandom groups: fast and simple
by: Derksen, Harm, et al.
Published: (2024)

Approximately counting maximal independent set is equivalent to #SAT
by: Zhang, Hao, et al.
Published: (2024)

Two-Source and Affine Non-Malleable Extractors for Small Entropy
by: Li, Xin, et al.
Published: (2024)