Copertina

The Log-Rank Conjecture: New Equivalent Formulations

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Hambardzumyan, Lianna, Lovett, Shachar, Shirley, Morgan
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Combinatorics
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Factorization norms and an inverse theorem for MaxCut
di: Balla, Igor, et al.
Pubblicazione: (2025)

The Rank-Ramsey Problem and the Log-Rank Conjecture
di: Beniamini, Gal, et al.
Pubblicazione: (2024)

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

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

Quasipolynomial bounds for the corners theorem
di: Jaber, Michael, et al.
Pubblicazione: (2025)

No Complete Problem for Constant-Cost Randomized Communication
di: Fang, Yuting, et al.
Pubblicazione: (2024)

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

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

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

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

Improved Parallel Repetition for GHZ-Supported Games via Spreadness
di: Liu, Yang P., et al.
Pubblicazione: (2026)

Graphs, Disjoint Matchings and Some Inequalities
di: Hambardzumyan, Lianna, et al.
Pubblicazione: (2015)

List Decoding Quotient Reed-Muller Codes
di: Gotlib, Omri, et al.
Pubblicazione: (2025)

Refuting approaches to the log-rank conjecture for XOR functions
di: Hatami, Hamed, et al.
Pubblicazione: (2023)

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

Characterizing and Testing Principal Minor Equivalence of Matrices
di: Chatterjee, Abhranil, et al.
Pubblicazione: (2024)

Equivalent Dichotomies for Triangle Detection in Subgraph, Induced, and Colored H-Free Graphs
di: Abboud, Amir, et al.
Pubblicazione: (2026)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
di: Seppelt, Tim
Pubblicazione: (2023)

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

Complexity Framework For Forbidden Subgraphs V: Beyond Simple Graphs
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2025)

Refuting Perfect Matchings in Spectral Expanders is Hard
di: Biswas, Ari, et al.
Pubblicazione: (2025)

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

Hunting a rabbit: complexity, approximability and some characterizations
di: Ben-Ameur, Walid, et al.
Pubblicazione: (2025)

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
di: Hodur, Nadzieja, et al.
Pubblicazione: (2025)

Improved Small Set Expansion in High Dimensional Expanders
di: Kaufman, Tali, et al.
Pubblicazione: (2025)

A near-optimal Quadratic Goldreich-Levin algorithm
di: Briët, Jop, et al.
Pubblicazione: (2025)

Assembly Addition Chains
di: Cronin, Leroy, et al.
Pubblicazione: (2025)

Tensor rank and dimension expanders
di: Dvir, Zeev
Pubblicazione: (2025)

Interactive Proofs For Distribution Testing With Conditional Oracles
di: Biswas, Ari, et al.
Pubblicazione: (2025)

Matchgate signatures under variable permutations
di: Meng, Boning, et al.
Pubblicazione: (2025)

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

Sensitivity and Hamming graphs
di: Asensio, Sara, et al.
Pubblicazione: (2025)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
di: Mittal, Kunal
Pubblicazione: (2025)

Finding a HIST: Chordality, Structural Parameters, and Diameter
di: Hanaka, Tesshu, et al.
Pubblicazione: (2025)

Factorization norms and Zarankiewicz problems
di: Tomon, István
Pubblicazione: (2025)

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

A Note on the Complexity of Directed Clique
di: Gutowski, Grzegorz, et al.
Pubblicazione: (2026)

Direct Product Primality Testing of Graphs is GI-hard
di: Calderoni, Luca, et al.
Pubblicazione: (2020)

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

Sparse juntas on the biased hypercube
di: Dinur, Irit, et al.
Pubblicazione: (2017)