Buchumschlag

What Juris Hartmanis taught me about Reductions

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Immerman, Neil
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

On the Number of Quantifiers Needed to Define Boolean Functions
von: Carmosino, Marco, et al.
Veröffentlicht: (2024)

Multi-Structural Games and Beyond
von: Carmosino, Marco, et al.
Veröffentlicht: (2023)

Parallel Play Saves Quantifiers
von: Carmosino, Marco, et al.
Veröffentlicht: (2024)

Recovery Reductions, Conjectures, and Barriers
von: Nareddy, Tejas, et al.
Veröffentlicht: (2025)

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
von: Brand, Cornelius, et al.
Veröffentlicht: (2026)

A Compendium of Reductions: reductions.network
von: Grüne, Christoph, et al.
Veröffentlicht: (2025)

Reductions Between Code Equivalence Problems
von: Cheraghchi, Mahdi, et al.
Veröffentlicht: (2025)

How to fit large complexity classes into TFNP
von: Thapen, Neil
Veröffentlicht: (2024)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
von: Arvind, Vikraman, et al.
Veröffentlicht: (2024)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
von: Wang, Cancan, et al.
Veröffentlicht: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
von: Ostonov, Azimkhon, et al.
Veröffentlicht: (2024)

On the consistency of stronger lower bounds for NEXP
von: Thapen, Neil
Veröffentlicht: (2025)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
von: Pfaue, Femke
Veröffentlicht: (2024)

Lines in Every Direction with No ee-Random Points
von: Lutz, Neil, et al.
Veröffentlicht: (2025)

A Subexponential Reduction from Product Partition to Subset Sum
von: Costandin, Marius
Veröffentlicht: (2024)

Specification and Automatic Verification of Computational Reductions
von: Grange, Julien, et al.
Veröffentlicht: (2024)

Modular Counting CSP: Reductions and Algorithms
von: Kazeminia, Amirhossein, et al.
Veröffentlicht: (2025)

What an RVU experiment taught me about Medical Physics
von: Timothy D. Solberg
Veröffentlicht: (2025)

ActionReasoningBench: Reasoning about Actions with and without Ramification Constraints
von: Handa, Divij, et al.
Veröffentlicht: (2024)

Gap Preserving Reductions Between Reconfiguration Problems
von: Ohsaka, Naoto
Veröffentlicht: (2022)

Information Redistribution Under Reductions in NP Search
von: Wei, Jing-Yuan
Veröffentlicht: (2026)

On Saxe's theorems about the complexity of the Distance Geometry Problem
von: Kupperschmitt, Maël, et al.
Veröffentlicht: (2025)

Hausdorff Reductions and the Exponential Hierarchies
von: Malizia, Enrico
Veröffentlicht: (2024)

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
von: Buhrman, Harry, et al.
Veröffentlicht: (2024)

Expected Complexity of Persistence Barcode Computation via Matrix Reduction
von: Giunti, Barbara, et al.
Veröffentlicht: (2021)

Automatizing Software Cognitive Complexity Reduction through Integer Linear Programming
von: Saborido, Rubén, et al.
Veröffentlicht: (2024)

Algorithmically Optimal Outer Measures
von: Lutz, Jack H., et al.
Veröffentlicht: (2020)

Epistemic Skills: Reasoning about Knowledge and Oblivion
von: Liang, Xiaolong, et al.
Veröffentlicht: (2025)

Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
von: Sim, Chee-Khian
Veröffentlicht: (2024)

Solving Four Open Problems about Core Stability in Altruistic Hedonic Games
von: Rothe, Jörg, et al.
Veröffentlicht: (2025)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
von: Delavenne, Hugo, et al.
Veröffentlicht: (2024)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
von: Balliu, Alkida, et al.
Veröffentlicht: (2025)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
von: Jansen, Bart M. P., et al.
Veröffentlicht: (2026)

What makes an Ensemble (Un) Interpretable?
von: Bassan, Shahaf, et al.
Veröffentlicht: (2025)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
von: Bodirsky, Manuel, et al.
Veröffentlicht: (2024)

Finding One Local Optimum Is Easy -- but What About Two?
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
von: Cheng, Kuan, et al.
Veröffentlicht: (2025)

Alphabet Reduction for Reconfiguration Problems
von: Ohsaka, Naoto
Veröffentlicht: (2024)

Algorithmic Information Bounds for Distances and Orthogonal Projections
von: Cholak, Peter, et al.
Veröffentlicht: (2025)

Learning Randomized Reductions
von: Erata, Ferhat, et al.
Veröffentlicht: (2024)