Cover Image

KRW Composition Theorems via Lifting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	de Rezende, Susanna F., Meir, Or, Nordström, Jakob, Pitassi, Toniann, Robere, Robert
Format:	Preprint
Published:	2020
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Toward Better Depth Lower Bounds: A KRW-like theorem for Strong Composition
by: Meir, Or
Published: (2023)

High Rate Efficient Local List Decoding from HDX
by: Dikstein, Yotam, et al.
Published: (2026)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
by: de Rezende, Susanna F., et al.
Published: (2024)

Lifting with Inner Functions of Polynomial Discrepancy
by: Manor, Yahel, et al.
Published: (2024)

DNF formulas are efficiently testable with relative error
by: Chen, Xi, et al.
Published: (2026)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

Testing Juntas and Junta Subclasses with Relative Error
by: Chen, Xi, et al.
Published: (2025)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

On Pigeonhole Principles and Ramsey in TFNP
by: Jain, Siddhartha, et al.
Published: (2024)

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

Deterministic Lifting Theorems for One-Way Number-on-Forehead Communication
by: Yang, Guangxu, et al.
Published: (2025)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

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

A Lifting Theorem for Hybrid Classical-Quantum Communication Complexity
by: Wu, Xudong, et al.
Published: (2025)

Average-Case Hardness of Binary-Encoded Clique in Proof and Communication Complexity
by: de Rezende, Susanna F., et al.
Published: (2026)

The Proof Analysis Problem
by: Arteche, Noel, et al.
Published: (2025)

A Distributional-Lifting Theorem for PAC Learning
by: Blanc, Guy, et al.
Published: (2025)

Lifting for Arbitrary Gadgets
by: Iyer, Siddharth
Published: (2025)

An Analytical Approach to Parallel Repetition via CSP Inverse Theorems
by: Bhangale, Amey, et al.
Published: (2025)

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

Gadgetless Lifting Beats Round Elimination: Improved Lower Bounds for Pointer Chasing
by: Mao, Xinyu, et al.
Published: (2024)

On Optimal Testing of Linearity
by: Arora, Vipul, et al.
Published: (2024)

Direct Product Theorems for Randomized Query Complexity
by: Ben-David, Shalev, et al.
Published: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
by: de Rezende, Susanna F., et al.
Published: (2024)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)

A Refinement of the McCreight-Meyer Union Theorem
by: Fox, Matthew, et al.
Published: (2024)

Lift-and-Project Integrality Gaps for Santa Claus
by: Bamas, Etienne
Published: (2024)

A Strong Direct Sum Theorem for Distributional Query Complexity
by: Blanc, Guy, et al.
Published: (2024)

Virtual Qudits for Simon's Problem: Dimension-Lifted Algorithms on Qubit Hardware
by: Semre, Abed, et al.
Published: (2025)

Improved Quantum Lifting by Coherent Measure-and-Reprogram
by: Cojocaru, Alexandru, et al.
Published: (2025)

Quantum Lifting for Invertible Permutations and Ideal Ciphers
by: Cojocaru, Alexandru, et al.
Published: (2025)

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

Fully-Fluctuating Participation in Sleepy Consensus
by: Efron, Yuval, et al.
Published: (2025)

Fagin's Theorem for Semiring Turing Machines
by: Badia, Guillermo, et al.
Published: (2025)

A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
by: Greilhuber, Jakob, et al.
Published: (2026)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
by: de Rezende, Susanna F., et al.
Published: (2026)

Two Simple Proofs of Müller's Theorem
by: Epstein, Samuel
Published: (2024)

A Zero-Knowledge PCP Theorem
by: Gur, Tom, et al.
Published: (2024)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

Cosystolic Expansion of Sheaves on Posets with Applications to Good 2-Query Locally Testable Codes and Lifted Codes
by: First, Uriya A., et al.
Published: (2024)