Cover Image

Resilient functions: Optimized, simplified, and generalized

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Ivanov, Peter, Viola, Emanuele
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

Some Applications and Limitations of Convex Optimization Hierarchies for Discrete and Continuous Optimization Problems
by: Ghosh, Mrinalkanti
Published: (2025)

A general framework for finding diverse solutions via network flow and its applications
by: Iwamasa, Yuni, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Dominating Set Knapsack: Profit Optimization on Dominating Sets
by: Singh, Sipra
Published: (2025)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
by: Kontogiannis, Andreas, et al.
Published: (2026)

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

Removable Online Knapsack and Advice
by: Böckenhauer, Hans-Joachim, et al.
Published: (2020)

Going Beyond Twin-width? CSPs with Unbounded Domain and Few Variables
by: Jonsson, Peter, et al.
Published: (2025)

Can You Link Up With Treewidth?
by: Curticapean, Radu, et al.
Published: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Simple approximation algorithms for Polyamorous Scheduling
by: Biktairov, Yuriy, et al.
Published: (2024)

Size Minimization For Multi-Output AND-Functions
by: Armbruster, Susanne
Published: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
by: Stoian, Mihail
Published: (2024)

Cluster Editing on Cographs and Related Classes
by: Lafond, Manuel, et al.
Published: (2024)

Improved Hardness-of-Approximation for Token Swapping
by: Hiken, Sam, et al.
Published: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

On the complexity and approximability of Bounded access Lempel Ziv coding
by: Cicalese, Ferdinando, et al.
Published: (2024)

Parameterized Vertex Integrity Revisited
by: Hanaka, Tesshu, et al.
Published: (2024)

On approximability of the Permanent of PSD matrices
by: Ebrahimnejad, Farzam, et al.
Published: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
by: Dong, Qingxiu, et al.
Published: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
by: Sato, Atsuki, et al.
Published: (2024)

Randomized query composition and product distributions
by: Sanyal, Swagato
Published: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
by: Heeger, Klaus, et al.
Published: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
by: Stoian, Mihail
Published: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
by: Kuschner, Jordan, et al.
Published: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
by: Yang, Yang
Published: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Solving Polynomial Equations Over Finite Fields
by: Dell, Holger, et al.
Published: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Rounding Large Independent Sets on Expanders
by: Bafna, Mitali, et al.
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Knapsack with Vertex Cover, Set Cover, and Hitting Set
by: Dey, Palash, et al.
Published: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
by: Frei, Fabian, et al.
Published: (2024)

Hardness Results on Characteristics for Elastic-Degenerated Strings
by: Köppl, Dominik, et al.
Published: (2024)

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)