:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bogdanov, Andrej, Rosen, Alon, Vafa, Neekon, Vaikuntanathan, Vinod
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computation Computational Complexity Data Structures and Algorithms
Online-Zugang:	https://arxiv.org/abs/2504.09331
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Symmetric Perceptrons, Number Partitioning and Lattices
von: Vafa, Neekon, et al.
Veröffentlicht: (2025)

The Planted Orthogonal Vectors Problem
von: Kühnemann, David, et al.
Veröffentlicht: (2025)

Average-Case Complexity of Quantum Stabilizer Decoding
von: Khesin, Andrey Boris, et al.
Veröffentlicht: (2025)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

Semi-Streaming Algorithms for Graph Property Certification
von: Das, Avinandan, et al.
Veröffentlicht: (2025)

On the Advantage of Adaptivity for Sampling with Cell Probes
von: Byramji, Farzan, et al.
Veröffentlicht: (2026)

On the complexity of global Roman domination problem in graphs
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2026)

Oblivious Defense in ML Models: Backdoor Removal without Detection
von: Goldwasser, Shafi, et al.
Veröffentlicht: (2024)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
von: Grandjean, Étienne, et al.
Veröffentlicht: (2025)

A computational phase transition for learning-to-sample from Ising models
von: Risteski, Andrej, et al.
Veröffentlicht: (2026)

Adaptive and oblivious statistical adversaries are equivalent
von: Blanc, Guy, et al.
Veröffentlicht: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

The Trichotomy of Regular Property Testing
von: Bathie, Gabriel, et al.
Veröffentlicht: (2025)

Downward self-reducibility in the total function polynomial hierarchy
von: Gajulapalli, Karthik, et al.
Veröffentlicht: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
von: Fujie, Yuto, et al.
Veröffentlicht: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
von: Moroie, Gregory
Veröffentlicht: (2025)

Precoloring extension with demands on paths
von: Das, Arun Kumar, et al.
Veröffentlicht: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
von: Gholizadeh, Hossein, et al.
Veröffentlicht: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
von: Herrmann, Anton, et al.
Veröffentlicht: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
von: Maalouly, Nicolas El, et al.
Veröffentlicht: (2025)

k-SUM Hardness Implies Treewidth-SETH
von: Lampis, Michael
Veröffentlicht: (2025)

Efficient Catalytic Graph Algorithms
von: Cook, James, et al.
Veröffentlicht: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
von: Dhar, Anubhav, et al.
Veröffentlicht: (2025)

Scheduling Problems with Constrained Rejections
von: Davies, Sami, et al.
Veröffentlicht: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
von: Uhlmann, Jeffrey
Veröffentlicht: (2025)

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

Geometric Interpretation of 3-SAT and Phase Transition
von: Gillet, Frederic
Veröffentlicht: (2025)

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

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
von: Curticapean, Radu, et al.
Veröffentlicht: (2025)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
von: Gaikwad, Ajinkya, et al.
Veröffentlicht: (2025)

Most Juntas Saturate the Hardcore Lemma
von: Kumar, Vinayak M.
Veröffentlicht: (2025)

FPT Parameterisations of Fractional and Generalised Hypertree Width
von: Lanzinger, Matthias, et al.
Veröffentlicht: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
von: Kluk, Kacper, et al.
Veröffentlicht: (2025)

Novel Complexity Results for Temporal Separators with Deadlines
von: Dondi, Riccardo, et al.
Veröffentlicht: (2025)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
von: Kurita, Kazuhiro, et al.
Veröffentlicht: (2025)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
von: Björklund, Andreas, et al.
Veröffentlicht: (2025)

Broadcasting under Structural Restrictions
von: Egami, Yudai, et al.
Veröffentlicht: (2025)

Randomized $\tilde{O}(m\sqrt{n})$ Bellman-Ford from Fineman and the Boilermakers
von: Rao, Satish
Veröffentlicht: (2025)