:: Library Catalog

Copertina

Salvato in:

Dettagli Bibliografici
Autori principali:	Bhadra, Ronak, Tewari, Raghunath
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	https://arxiv.org/abs/2409.18469
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Lossy Catalytic Computation
di: Gupta, Chetan, et al.
Pubblicazione: (2024)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
di: Gupta, Chetan, et al.
Pubblicazione: (2025)

On Solving Reachability in Grid Digraphs using a Psuedoseparator
di: Jain, Rahul, et al.
Pubblicazione: (2019)

Trading Determinism for Noncommutativity in Edmonds' Problem
di: Arvind, V., et al.
Pubblicazione: (2024)

Quantum Statistical Witness Indistinguishability
di: Nassar, Shafik, et al.
Pubblicazione: (2025)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
di: Yung, Kingsley
Pubblicazione: (2024)

Average-Case Hardness of Parity Problems: Orthogonal Vectors, k-SUM and More
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2025)

Quantum k-SAT Related Hypergraph Problems
di: Kremer, Simon-Luca, et al.
Pubblicazione: (2025)

Determination Problems for Orbit Closures and Matrix Groups
di: Manssour, Rida Ait El, et al.
Pubblicazione: (2024)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
di: Yi, Yongming
Pubblicazione: (2026)

Quantum Learning Theory Beyond Batch Binary Classification
di: Mohan, Preetham, et al.
Pubblicazione: (2023)

Quantum Search with In-Place Queries
di: Holman, Blake, et al.
Pubblicazione: (2025)

Analogy between List Coloring Problems and the Interval $k$-$(γ,μ)$-choosability property: theoretical aspects of complexity
di: Gama, Simone Ingrid Monteiro, et al.
Pubblicazione: (2025)

PDQMA = DQMA = NEXP: QMA With Hidden Variables and Non-collapsing Measurements
di: Aaronson, Scott, et al.
Pubblicazione: (2024)

Network Satisfaction Problems Solved by k-Consistency
di: Bodirsky, Manuel, et al.
Pubblicazione: (2023)

Learning Read-Once Determinants and the Principal Minor Assignment Problem
di: Aravind, Abhiram, et al.
Pubblicazione: (2026)

On the Hardness of Approximation of the Fair k-Center Problem
di: Thejaswi, Suhas
Pubblicazione: (2026)

A Critique of Chen's "The 2-MAXSAT Problem Can Be Solved in Polynomial Time"
di: Le, Tran Duy Anh, et al.
Pubblicazione: (2024)

Complexity of Paired Domination Problems on Circle and $k$-Polygon Graphs
di: Mu, Ta-Yu, et al.
Pubblicazione: (2024)

On Approximability of Satisfiable k-CSPs: V
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

Near Optimal Hardness of Approximating $k$-CSP
di: Minzer, Dor, et al.
Pubblicazione: (2025)

Width Hierarchy for k-OBDD of Small Width
di: Khadiev, Kamil
Pubblicazione: (2015)

On the Complexity of the Minimum-($k,ρ$)-Shortcut Problem
di: Avila, Tatiana Rocha, et al.
Pubblicazione: (2026)

On Extremal Properties of k-CNF: Capturing Threshold Functions
di: Gurumukhani, Mohit, et al.
Pubblicazione: (2024)

Constant-Cost Communication is not Reducible to k-Hamming Distance
di: Fang, Yuting, et al.
Pubblicazione: (2024)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
di: S., Karthik C., et al.
Pubblicazione: (2021)

A Simpler Exponential-Time Approximation Algorithm for MAX-k-SAT
di: Buhrman, Harry, et al.
Pubblicazione: (2025)

On the Principal Minor Expansion and Complexity of the Symmetrized Determinant
di: Agarwal, Sanyam, et al.
Pubblicazione: (2026)

On Approximability of Satisfiable $k$-CSPs: VI
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
di: Bhangale, Amey, et al.
Pubblicazione: (2024)

On Approximability of Satisfiable k-CSPs: IV
di: Bhangale, Amey, et al.
Pubblicazione: (2023)

There is a Hyper-Greedoid lurking behind every Graphical Accessible Computational Search Problem solvable in Polynomial Time: $P \not= NP$
di: Kayibi, Koko-Kalambay Kalafan
Pubblicazione: (2018)

On Computability of Computable Problems
di: Khaliq, Asad
Pubblicazione: (2023)

The Stochastic Arrival Problem
di: Webster, Thomas
Pubblicazione: (2022)

PCPP-Based Reconfiguration Inapproximability: Query Complexity vs. Soundness Gap Trade-offs
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2025)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
di: Błasiok, Jarosław, et al.
Pubblicazione: (2026)

Trade-offs between Entanglement and Communication
di: Arunachalam, Srinivasan, et al.
Pubblicazione: (2023)

On the Hierarchies for Deterministic, Nondeterministic and Probabilistic Ordered Read-k-times Branching Programs
di: Khadiev, Kamil
Pubblicazione: (2016)

The Greedy Coin Change Problem
di: Gupta, Shreya, et al.
Pubblicazione: (2024)

On the Hardness of the Drone Delivery Problem
di: Bartlmae, Simon, et al.
Pubblicazione: (2025)