:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Keshavan, Anand Kumar, Engineer, Sunu
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2506.18921
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The status of the quantum PCP conjecture (games version)
by: Natarajan, Anand, et al.
Published: (2024)

Transcendental Okounkov bodies
by: Darvas, Tamás, et al.
Published: (2023)

Transcendental meromorphic solutions and the complex Schrödinger equation with delay
by: Cao, Tingbin, et al.
Published: (2025)

Periodicity of Transcendental Entire Functions Sharing Set with their Shifts
by: Roy, Soumon, et al.
Published: (2025)

Transcendental Minimal Model Program for Projective Varieties
by: Das, Omprokash, et al.
Published: (2024)

On the Exceptional Set of Transcendental Entire Functions in Several Variables
by: Alves, Diego, et al.
Published: (2023)

Hardness of Random Reordered Encodings of Parity for Resolution and CDCL
by: Chew, Leroy, et al.
Published: (2024)

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

Transcendental b-divisors II -- Monotonicity theorem
by: Xia, Mingchen
Published: (2026)

Transcendental b-divisors I -- Correspondence with currents
by: Xia, Mingchen
Published: (2026)

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

On Dynamics of the Bungee set and the Filled Julia set of a Transcendental Semigroup
by: Kumari, Manisha, et al.
Published: (2025)

Near-Optimal Encodings of Cardinality Constraints
by: Krapivin, Andrew, et al.
Published: (2026)

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
by: Li, Songsong, et al.
Published: (2024)

Two bases suffice for QMA1-completeness
by: Ma, Henry, et al.
Published: (2025)

Thermodynamic Formalism for a Class of Hyperbolic Transcendental Meromorphic Functions
by: Naderiyan, Hamid
Published: (2025)

Structure-Aware Encodings of Argumentation Properties for Clique-width
by: Mahmood, Yasir, et al.
Published: (2025)

Collapses in quantum-classical probabilistically checkable proofs and the quantum polynomial hierarchy
by: Anand, Kartik, et al.
Published: (2025)

On the Minimum Depth of Circuits with Linear Number of Wires Encoding Good Codes
by: Drucker, Andrew, et al.
Published: (2024)

Finding dense sub-lattices as low-energy states of a Hamiltonian
by: Barberà-Rodríguez, Júlia, et al.
Published: (2023)

Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false
by: Watts, Adam Bene, et al.
Published: (2025)

A Relativizing MIP for BQP
by: Aaronson, Scott, et al.
Published: (2026)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
by: Singer, Noah G.
Published: (2025)

Rethinking the Role of Positional Encoding: Sliding-Window Transformers without PE Remain Turing Complete
by: Li, Qian, et al.
Published: (2026)

Encoding Co-Lex Orders of Finite-State Automata in Linear Space
by: Becker, Ruben, et al.
Published: (2025)

New Pseudorandom Generators and Correlation Bounds Using Extractors
by: Kumar, Vinayak M.
Published: (2025)

A proof of Ollinger's conjecture: undecidability of tiling the plane with a set of $8$ polyominoes
by: Yang, Chao, et al.
Published: (2024)

Transcendental Julia Sets of Minimal Hausdorff Dimension
by: Burkart, Jack, et al.
Published: (2021)

On the two conjectures
by: Sarkar, Nabadwip, et al.
Published: (2025)

Low degree conjecture implies sharp computational thresholds in stochastic block model
by: Ding, Jingqiu, et al.
Published: (2025)

The Computational Advantage of MIP* Vanishes in the Presence of Noise
by: Dong, Yangjing, et al.
Published: (2023)

When Majority Fails: Tight Bounds for Correlation Distillation Conjectures
by: Kamath, Pritish, et al.
Published: (2026)

Rank Bounds and PIT for $Σ^3 ΠΣΠ^d$ circuits via a non-linear Edelstein-Kelly theorem
by: Garg, Abhibhav, et al.
Published: (2025)

If VNP is hard, then so are equations for it
by: Kumar, Mrinal, et al.
Published: (2020)

On Zalcman's and Bieberbach conjectures
by: Krushkal, Samuel L.
Published: (2026)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
by: Grigorescu, Elena, et al.
Published: (2025)

MaxMin Separation Problems: FPT Algorithms for $st$-Separator and Odd Cycle Transversal
by: Gaikwad, Ajinkya, et al.
Published: (2025)

Identifying Codes Kernelization Limitations
by: Banik, Aritra, et al.
Published: (2025)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

Rounding Almost Commuting Hamiltonians
by: Faisal, Islam, et al.
Published: (2026)