Buchumschlag

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Tzameret, Iddo, Zhang, Lu-Ming
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Computational Complexity Combinatorics 03D15, 68Q10, 68Q15 F.1.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

NP-hard problems are not in BQP
von: Czerwinski, Reiner
Veröffentlicht: (2023)

Separation of PSPACE and EXP
von: Czerwinski, Reiner
Veröffentlicht: (2021)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
von: Hakoniemi, Tuomas, et al.
Veröffentlicht: (2024)

Simulating Polynomial-Time Nondeterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2024)

Meta Theorem for Hardness on FCP-Problem
von: Nagao, Atsuki, et al.
Veröffentlicht: (2025)

Upper and Lower Bounds for the Linear Ordering Principle
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

Linear Matroid Intersection is in Catalytic Logspace
von: Agarwala, Aryan, et al.
Veröffentlicht: (2025)

Oracle Separations for RPH
von: Hamm, Thekla, et al.
Veröffentlicht: (2025)

Sign-Rank of $k$-Hamming Distance is Constant
von: Göös, Mika, et al.
Veröffentlicht: (2025)

A Note on Avoid vs MCSP
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
von: Garcia, Baruch
Veröffentlicht: (2026)

The Polynomial Hierarchy does not collapse
von: Czerwinski, Reiner
Veröffentlicht: (2024)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
von: Huseynzade, Rafig
Veröffentlicht: (2025)

Evolomino is NP-complete
von: Nikolaev, Andrei V.
Veröffentlicht: (2025)

#P is Sandwiched by One and Two #2DNF Calls: Is Subtraction Stronger Than We Thought?
von: Bannach, Max, et al.
Veröffentlicht: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
von: Shalunov, Yakov
Veröffentlicht: (2023)

Insignificant Choice Polynomial Time: A Logic Capturing PTIME
von: Schewe, Klaus-Dieter
Veröffentlicht: (2020)

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

Generalisations of Matrix Partitions : Complexity and Obstructions
von: Barsukov, Alexey, et al.
Veröffentlicht: (2021)

The Serial Scaling Hypothesis
von: Liu, Yuxi, et al.
Veröffentlicht: (2025)

The Optimizer Quotient and the Certification Trilemma
von: Simas, Tristan
Veröffentlicht: (2026)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)

A Logspace Constructive Proof of L=SL
von: Buss, Sam, et al.
Veröffentlicht: (2025)

Choiceless Polynomial Space
von: Ferrarotti, Flavio, et al.
Veröffentlicht: (2024)

Exploring P versus NP
von: Tang, Jian-Gang
Veröffentlicht: (2022)

A correspondence between the time and space complexity
von: Latkin, Ivan V.
Veröffentlicht: (2023)

The Solver's Paradox in Formal Problem Spaces
von: Rosko, Milan
Veröffentlicht: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
von: Kelley, Zander, et al.
Veröffentlicht: (2023)

The Complexity of Iterated Reversible Computation
von: Eppstein, David
Veröffentlicht: (2021)

Completeness classes in algebraic complexity theory
von: Bürgisser, Peter
Veröffentlicht: (2024)

An MDL-Style Cost Functional KC, Distribution-Preserving Reductions ($A2^d$), and an $AC^0$+log Lower Bound for 3SAT via Balanced 3XOR
von: Lela, Marko
Veröffentlicht: (2025)

Some derivations among Logarithmic Space Bounded Counting Classes
von: Janaki, V., et al.
Veröffentlicht: (2023)

Why the classes P and NP are not well-defined finitarily
von: Anand, Bhupinder Singh
Veröffentlicht: (2024)

Complexities of Well-Quasi-Ordered Substructural Logics
von: Galatos, Nikolaos, et al.
Veröffentlicht: (2025)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
von: Lin, Tianrong
Veröffentlicht: (2023)

From Gödel incompleteness to the consistency of circuit lower bounds
von: Atserias, Albert, et al.
Veröffentlicht: (2026)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
von: Saffidine, Abdallah, et al.
Veröffentlicht: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Diagonalization of Polynomial-Time Deterministic Turing Machines via Nondeterministic Turing Machines
von: Lin, Tianrong
Veröffentlicht: (2021)

Failure of the strong feasible disjunction property
von: Krajicek, Jan
Veröffentlicht: (2026)