:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Fei, Yumou, Goldberg, Leslie Ann, Lu, Pinyan
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2309.04735
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
by: Focke, Jacob, et al.
Published: (2021)

Testing Properties of Edge Distributions
by: Fei, Yumou
Published: (2026)

Unbounded-width CSPs are Untestable in a Sublinear Number of Queries
by: Fei, Yumou
Published: (2025)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Counting Subgraphs in Somewhere Dense Graphs
by: Bressan, Marco, et al.
Published: (2022)

Inapproximability of the independent set polynomial in the complex plane
by: Bezakova, Ivona, et al.
Published: (2017)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

A Provable Expressiveness Hierarchy in Hybrid Linear-Full Attention
by: Ye, Xiaowei, et al.
Published: (2026)

Efficient Algorithms for Weakly-Interacting Quantum Spin Systems
by: Mann, Ryan L., et al.
Published: (2026)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

The Complexity of Computing KKT Solutions of Quadratic Programs
by: Fearnley, John, et al.
Published: (2023)

Multi-Prover Interactive Proof Systems with Leakage
by: Asadi, Vahid R., et al.
Published: (2026)

On the Nature and Complexity of an Impartial Two-Player Variant of the Game Lights-Out
by: Fiorini, Eugene, et al.
Published: (2024)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Pointer Chasing with Unlimited Interaction
by: Fischer, Orr, et al.
Published: (2025)

Boolean Circuit Complexity and Two-Dimensional Cover Problems
by: Cavalar, Bruno P., et al.
Published: (2025)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
by: Dvořák, Pavel, et al.
Published: (2024)

From Proof Complexity to Circuit Complexity via Interactive Protocols
by: Arteche, Noel, et al.
Published: (2024)

Domination in Diameter-Two Graphs and the 2-Club Cluster Vertex Deletion Parameter
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

The Power of Negation in Higher-Order Datalog
by: Charalambidis, Angelos, et al.
Published: (2025)

Coherent-State Propagation: A Computational Framework for Simulating Bosonic Quantum Systems
by: Guseynov, Nikita, et al.
Published: (2026)

Computing Equilibrium Points of Electrostatic Potentials
by: Ghosh, Abheek, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

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

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

Quantum Interactive Oracle Proofs
by: Sun, Baocheng, et al.
Published: (2026)

Order Retrieval in Compact Storage Systems
by: Fliedner, Malte, et al.
Published: (2025)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

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

Two Quantum Paradigms, but Still No Signal
by: Epstein, Samuel
Published: (2024)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Complexity of Unambiguous Problems in $Σ^P_2$
by: Gilboa, Matan, et al.
Published: (2025)

Optimal Coding for Randomized Kolmogorov Complexity and Its Applications
by: Hirahara, Shuichi, et al.
Published: (2024)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
by: Lu, Jiaqi, et al.
Published: (2025)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Complexity of the Guarded Two-Variable Fragment with Counting Quantifiers
by: Pratt-Hartmann, Ian
Published: (2006)

Efficiently Batching Unambiguous Interactive Proofs
by: Berger, Bonnie, et al.
Published: (2025)

Two prover perfect zero knowledge for MIP*
by: Mastel, Kieran, et al.
Published: (2024)