Copertina

Sampling Permutations with Cell Probes is Hard

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Alekseev, Yaroslav, Göös, Mika, Myasnikov, Konstantin, Riazanov, Artur, Sokolov, Dmitry
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Better Boosting of Communication Oracles, or Not
di: Harms, Nathaniel, et al.
Pubblicazione: (2024)

On the Advantage of Adaptivity for Sampling with Cell Probes
di: Byramji, Farzan, et al.
Pubblicazione: (2026)

Improved Algorithm for Permutation Testing
di: Zhang, Xiaojin
Pubblicazione: (2020)

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

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
di: Ko, Young Kun
Pubblicazione: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
di: Bai, Tian, et al.
Pubblicazione: (2026)

Top-Down Lower Bounds for Depth-Four Circuits
di: Göös, Mika, et al.
Pubblicazione: (2023)

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

Hardness of Dynamic Core and Truss Decompositions
di: Couto, Yan S., et al.
Pubblicazione: (2025)

Algorithms and Hardness for Estimating Statistical Similarity
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

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

k-SUM Hardness Implies Treewidth-SETH
di: Lampis, Michael
Pubblicazione: (2025)

Hardness and Algorithmic Results for Roman \{3\}-Domination
di: Reddy, Sangam Balchandar
Pubblicazione: (2025)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

Sumplete is Hard, Even with Two Different Numbers
di: Ruangwises, Suthee
Pubblicazione: (2023)

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

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

Capacitated Fair-Range Clustering: Hardness and Approximation Algorithms
di: Gadekar, Ameet, et al.
Pubblicazione: (2025)

Hardness and Tractability of T_{h+1}-Free Edge Deletion
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2026)

Counting Small Induced Subgraphs: Hardness via Fourier Analysis
di: Curticapean, Radu, et al.
Pubblicazione: (2024)

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
di: Adriaens, Florian, et al.
Pubblicazione: (2024)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2025)

Testing Sumsets is Hard
di: Chen, Xi, et al.
Pubblicazione: (2024)

Deciding if a DAG is Interesting is Hard
di: De Carufel, Jean-Lou, et al.
Pubblicazione: (2025)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
di: Gribanov, Dmitry, et al.
Pubblicazione: (2022)

Bounded Independence Edge Sampling for Combinatorial Graph Properties
di: Putterman, Aaron, et al.
Pubblicazione: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
di: Yoshida, Yuichi, et al.
Pubblicazione: (2025)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
di: Huang, Neng, et al.
Pubblicazione: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
di: Garg, Sumegha, et al.
Pubblicazione: (2026)

Hardness of Median and Center in the Ulam Metric
di: Fischer, Nick, et al.
Pubblicazione: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
di: Kocurek, Nicholas, et al.
Pubblicazione: (2026)

Improved Hardness of Approximation for Geometric Bin Packing
di: Ray, Arka, et al.
Pubblicazione: (2023)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
di: Levet, Michael, et al.
Pubblicazione: (2025)

Sorting by Strip Swaps is NP-Hard
di: Roy, Swapnoneel, et al.
Pubblicazione: (2025)

Dequantization and Hardness of Spectral Sum Estimation
di: Edenhofer, Roman, et al.
Pubblicazione: (2025)

Hardness of Maximum Likelihood Learning of DPPs
di: Grigorescu, Elena, et al.
Pubblicazione: (2022)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
di: Moka, Sarat, et al.
Pubblicazione: (2026)