:: Library Catalog

Cover Image

Saved in:

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

Similar Items

On the Number of Quantifiers Needed to Define Boolean Functions
by: Carmosino, Marco, et al.
Published: (2024)

Multi-Structural Games and Beyond
by: Carmosino, Marco, et al.
Published: (2023)

Parallel Play Saves Quantifiers
by: Carmosino, Marco, et al.
Published: (2024)

Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
by: Brand, Cornelius, et al.
Published: (2026)

Recovery Reductions, Conjectures, and Barriers
by: Nareddy, Tejas, et al.
Published: (2025)

How to fit large complexity classes into TFNP
by: Thapen, Neil
Published: (2024)

A Compendium of Reductions: reductions.network
by: Grüne, Christoph, et al.
Published: (2025)

Reductions Between Code Equivalence Problems
by: Cheraghchi, Mahdi, et al.
Published: (2025)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
by: Arvind, Vikraman, et al.
Published: (2024)

What an RVU experiment taught me about Medical Physics
by: Timothy D. Solberg
Published: (2025)

A New Reduction Method from Multivariate Polynomials to Univariate Polynomials
by: Wang, Cancan, et al.
Published: (2024)

Lower Bounds on Cardinality of Reducts for Decision Tables from Closed Classes
by: Ostonov, Azimkhon, et al.
Published: (2024)

Lines in Every Direction with No ee-Random Points
by: Lutz, Neil, et al.
Published: (2025)

Specification and Automatic Verification of Computational Reductions
by: Grange, Julien, et al.
Published: (2024)

Modular Counting CSP: Reductions and Algorithms
by: Kazeminia, Amirhossein, et al.
Published: (2025)

Exploring the Reductions Between SSP-NP-complete Problems and Developing a Compendium Website Displaying the Results
by: Pfaue, Femke
Published: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
by: Costandin, Marius
Published: (2024)

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

ActionReasoningBench: Reasoning about Actions with and without Ramification Constraints
by: Handa, Divij, et al.
Published: (2024)

Gap Preserving Reductions Between Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2022)

Information Redistribution Under Reductions in NP Search
by: Wei, Jing-Yuan
Published: (2026)

Epistemic Skills: Reasoning about Knowledge and Oblivion
by: Liang, Xiaolong, et al.
Published: (2025)

Hausdorff Reductions and the Exponential Hierarchies
by: Malizia, Enrico
Published: (2024)

Algorithmically Optimal Outer Measures
by: Lutz, Jack H., et al.
Published: (2020)

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

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Expected Complexity of Persistence Barcode Computation via Matrix Reduction
by: Giunti, Barbara, et al.
Published: (2021)

Automatizing Software Cognitive Complexity Reduction through Integer Linear Programming
by: Saborido, Rubén, et al.
Published: (2024)

Reduction from the partition problem: Dynamic lot sizing problem with polynomial complexity
by: Sim, Chee-Khian
Published: (2024)

Quantum State Synthesis: Relation with Decision Complexity Classes and Impossibility of Synthesis Error Reduction
by: Delavenne, Hugo, et al.
Published: (2024)

What makes an Ensemble (Un) Interpretable?
by: Bassan, Shahaf, et al.
Published: (2025)

New Hardness Results for the LOCAL Model via a Simple Self-Reduction
by: Balliu, Alkida, et al.
Published: (2025)

Symmetric Linear Arc Monadic Datalog and Gadget Reductions
by: Bodirsky, Manuel, et al.
Published: (2024)

Search-space Reduction for Boolean MinCSPs via Essential Constraints
by: Jansen, Bart M. P., et al.
Published: (2026)

Finding One Local Optimum Is Easy -- but What About Two?
by: Kobayashi, Yasuaki, et al.
Published: (2025)

Alphabet Reduction for Reconfiguration Problems
by: Ohsaka, Naoto
Published: (2024)

Weighted Pseudorandom Generators for Read-Once Branching Programs via Weighted Pseudorandom Reductions
by: Cheng, Kuan, et al.
Published: (2025)

Learning Randomized Reductions
by: Erata, Ferhat, et al.
Published: (2024)

Impossibility of Depth Reduction in Explainable Clustering
by: Deng, Chengyuan, et al.
Published: (2023)