:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Ishizuka, Takashi
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2312.04051
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The PPP-completeness of the Ward-Szabo theorem
by: Ishizuka, Takashi
Published: (2025)

PLS-completeness of string permutations
by: Scheder, Dominik, et al.
Published: (2025)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
by: Scheder, Dominik, et al.
Published: (2025)

Quantum algorithms for path and cycle containment problems
by: Cornelissen, Arjan, et al.
Published: (2026)

Corrigendum to "On the heterogeneous distortion inequality"
by: Kangasniemi, Ilmari, et al.
Published: (2023)

Tractability results for integration in subspaces of the Wiener algebra
by: Dick, Josef, et al.
Published: (2024)

Corrigendum to “Western North American Cruise Shipping Network: Space Structure and System”
Published: (2025)

Corrigendum to "On the monophonic rank of a graph" [Discrete Math. Theor. Comput. Sci. 24:2 (2022) #3]
by: Dourado, Mitre C., et al.
Published: (2023)

Quantum Advantage from One-Way Functions
by: Morimae, Tomoyuki, et al.
Published: (2023)

Verifiable Quantum Advantage without Structure
by: Yamakawa, Takashi, et al.
Published: (2022)

A Note on Output Length of One-Way State Generators and EFIs
by: Hhan, Minki, et al.
Published: (2023)

Quantum Cryptography and Hardness of Non-Collapsing Measurements
by: Morimae, Tomoyuki, et al.
Published: (2025)

From Worst-Case Hardness of $\mathsf{NP}$ to Quantum Cryptography via Quantum Indistinguishability Obfuscation
by: Morimae, Tomoyuki, et al.
Published: (2025)

Classical vs Quantum Advice and Proofs under Classically-Accessible Oracle
by: Li, Xingjian, et al.
Published: (2023)

Quantum Public-Key Encryption with Tamper-Resilient Public Keys from One-Way Functions
by: Kitagawa, Fuyuki, et al.
Published: (2023)

Proofs of quantum memory
by: Hhan, Minki, et al.
Published: (2025)

Corrigendum to “Funnel‐Based Adaptive Neural Fault‐Tolerant Control for Nonlinear Systems with Dead‐Zone and Actuator Faults: Application to Rigid Robot Manipulator and Inverted Pendulum Systems”
by: Ymnah Alruwaily, et al.
Published: (2025)

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

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Football as Foraging? Movements by Individual Players and Whole Teams Exhibit Lévy Walk Dynamics
by: Ivan Shpurov, et al.
Published: (2024)

An Overview of the Theory of Instances Computational Complexity
by: Jorge A. Ruiz-Vanoye
Published: (2011)

Computational Complexity of Swish
by: Horiyama, Takashi, et al.
Published: (2026)

Tensor Ranks and the Fine-Grained Complexity of Dynamic Programming
by: Alman, Josh, et al.
Published: (2023)

Baby PIH: Parameterized Inapproximability of Min CSP
by: Guruswami, Venkatesan, et al.
Published: (2023)

Scheme-Theoretic Approach to Computational Complexity. IV. A New Perspective on Hardness of Approximation
by: Çivril, Ali
Published: (2023)

Top-Down Lower Bounds for Depth-Four Circuits
by: Göös, Mika, et al.
Published: (2023)

Two-State Spin Systems with Negative Interactions
by: Fei, Yumou, et al.
Published: (2023)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Heuristics Optimization of Boolean Circuits with application in Attribute Based Encryption
by: Ionita, Alexandru, et al.
Published: (2023)

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

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

On the Existence of Seedless Condensers: Exploring the Terrain
by: Chattopadhyay, Eshan, et al.
Published: (2023)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)

On Computability of Computable Problems
by: Khaliq, Asad
Published: (2023)

One-Way Communication Complexity of Partial XOR Functions
by: Podolskii, Vladimir V., et al.
Published: (2023)

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

Extractors for Polynomial Sources over $\mathbb{F}_2$
by: Chattopadhyay, Eshan, et al.
Published: (2023)

On the Chow-rank of the permanent
by: Xu, Rongyu, et al.
Published: (2023)

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

Deterministic and Strongly Nondeterministic Decision Trees for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2023)