Cover Image

Lifting for Arbitrary Gadgets

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Iyer, Siddharth
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An XOR Lemma for Deterministic Communication Complexity
by: Iyer, Siddharth, et al.
Published: (2024)

XOR Lemmas for Communication via Marginal Information
by: Iyer, Siddharth, et al.
Published: (2023)

Pushing Blocks via Checkable Gadgets: PSPACE-completeness of Push-1F and Block/Box Dude
by: Ani, Hayashi, et al.
Published: (2024)

SAT, Gadgets, Max2XOR, and Quantum Annealers
by: Ansótegui, Carlos, et al.
Published: (2024)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
by: Bodirsky, Manuel, et al.
Published: (2024)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

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

KRW Composition Theorems via Lifting
by: de Rezende, Susanna F., et al.
Published: (2020)

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

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

Planarizing Gadgets for (k, l)-tight Graphs Do Not Exist
by: Chauhan, Archit, et al.
Published: (2026)

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

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

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

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

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)

Tight Time Complexities in Parallel Stochastic Optimization with Arbitrary Computation Dynamics
by: Tyurin, Alexander
Published: (2024)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

Pseudoentanglement Ain't Cheap
by: Grewal, Sabee, et al.
Published: (2024)

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

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)

A List of Complexity Bounds for Property Testing by Quantum Sample-to-Query Lifting
by: Chen, Kean, et al.
Published: (2025)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
by: Aaronson, Scott, et al.
Published: (2024)

Efficient Quantum Hermite Transform
by: Jain, Siddhartha, et al.
Published: (2025)

Testing Spreading Behavior in Networks with Arbitrary Topologies
by: Modanese, Augusto, et al.
Published: (2023)

Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom
by: Grewal, Sabee, et al.
Published: (2022)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
by: Harvey, Nicholas, et al.
Published: (2024)

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
by: Bhandari, Siddharth, et al.
Published: (2021)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

Improved Stabilizer Estimation via Bell Difference Sampling
by: Grewal, Sabee, et al.
Published: (2023)

Taming Barren Plateaus in Arbitrary Parameterized Quantum Circuits without Sacrificing Expressibility
by: Chen, Zhenyu, et al.
Published: (2025)

On Finding Randomly Planted Cliques in Arbitrary Graphs
by: Agrimonti, Francesco, et al.
Published: (2025)

Quantum Lower Bounds by Sample-to-Query Lifting
by: Wang, Qisheng, et al.
Published: (2023)

A Note on the Complexity of Bilevel Linear Programs in Fixed Dimensions
by: Ketkov, Sergey S., et al.
Published: (2025)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

Arithmetic Circuits with Division
by: Sacher, Silas Cato
Published: (2025)

Algorithmic Structure in Subset Sum: Deterministic In-Bound Navigation and the Counting Complexity Divide
by: Nkosi, Thami
Published: (2025)

The Line Traveling Salesman and Repairman Problem with Collaboration
by: Golak, Julian, et al.
Published: (2025)

Worst-Case and Average-Case Hardness of Hypercycle and Database Problems
by: Fu, Cheng-Hao, et al.
Published: (2025)