Cover Image

Leakage-Resilient Hardness Equivalence to Logspace Derandomization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Shalunov, Yakov
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity 68Q15 (Primary) 68Q25, 68Q87 (Secondary) F.1.3; G.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

Shifted Partial Derivative Polynomial Rank and Codimension
by: Edwards, Darren J.
Published: (2025)

Meta Theorem for Hardness on FCP-Problem
by: Nagao, Atsuki, et al.
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

Upper and Lower Bounds for the Linear Ordering Principle
by: Hirsch, Edward A., et al.
Published: (2025)

Oracle Separations for RPH
by: Hamm, Thekla, et al.
Published: (2025)

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

A Note on Avoid vs MCSP
by: Hirsch, Edward A., et al.
Published: (2025)

Diagonalization Without Relativization A Closer Look at the Baker-Gill-Solovay Theorem
by: Garcia, Baruch
Published: (2026)

Generalisations of Matrix Partitions : Complexity and Obstructions
by: Barsukov, Alexey, et al.
Published: (2021)

Stretching Demi-Bits and Nondeterministic-Secure Pseudorandomness
by: Tzameret, Iddo, et al.
Published: (2023)

An SoS Entropy Dichotomy via Windowed Hypercontractivity
by: Lela, Marko
Published: (2025)

Psi-Turing Machines: Bounded Introspection for Complexity Barriers and Oracle Separations
by: Huseynzade, Rafig
Published: (2025)

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hard
by: Dorochko, Leonid, et al.
Published: (2026)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Computational Complexity of Determining the Assembly Index
by: Masierak, Piotr
Published: (2026)

The Serial Scaling Hypothesis
by: Liu, Yuxi, et al.
Published: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
by: Kelley, Zander, et al.
Published: (2023)

Formal Foundations for Controlled Stochastic Activity Networks
by: Movaghar, Ali
Published: (2025)

The Solver's Paradox in Formal Problem Spaces
by: Rosko, Milan
Published: (2025)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Required-edge Cycle Cover Problem: an ASP-Completeness Framework for Graph Problems and Puzzles
by: Susukita, Kosuke, et al.
Published: (2026)

Hive is PSPACE-Hard
by: Andel, Daniël, et al.
Published: (2025)

ETH-Tight Complexity of Optimal Morse Matching on Bounded-Treewidth Complexes
by: Philip, Geevarghese, et al.
Published: (2026)

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

Weighted Automata and Logics Meet Computational Complexity
by: Kostolányi, Peter
Published: (2023)

NP-hard problems are not in BQP
by: Czerwinski, Reiner
Published: (2023)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Undefinability of Approximation of 2-to-2 Games
by: Dawar, Anuj, et al.
Published: (2025)

Runtime Analyses of NSGA-III on Many-Objective Problems
by: Opris, Andre, et al.
Published: (2024)

Achieving Tight $O(4^k)$ Runtime Bounds on Jump$_k$ by Proving that Genetic Algorithms Evolve Near-Maximal Population Diversity
by: Opris, Andre, et al.
Published: (2024)

A First Runtime Analysis of the PAES-25: An Enhanced Variant of the Pareto Archived Evolution Strategy
by: Opris, Andre
Published: (2025)

Separation of PSPACE and EXP
by: Czerwinski, Reiner
Published: (2021)

Finitely (In)tractable Promise Constraint Satisfaction Problems
by: Asimi, Kristina, et al.
Published: (2020)

Polynomial Prenexing of QBFs with Non-Monotone Boolean Operators
by: Saffidine, Abdallah, et al.
Published: (2025)

Dichotomy for orderings?
by: Kun, Gábor, et al.
Published: (2025)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)