Cover Image

Limitations of Stochastic Selection with Pairwise Independent Priors

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Dughmi, Shaddin, Kalayci, Yusuf Hakan, Patel, Neel
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Near-Optimal Sparsifiers for Stochastic Knapsack and Assignment Problems
by: Dughmi, Shaddin, et al.
Published: (2025)

Is Transductive Learning Equivalent to PAC Learning?
by: Dughmi, Shaddin, et al.
Published: (2024)

PAC Learning is just Bipartite Matching (Sort of)
by: Dughmi, Shaddin
Published: (2025)

Pairwise-Independent Contention Resolution
by: Gupta, Anupam, et al.
Published: (2024)

Transductive Learning Is Compact
by: Asilis, Julian, et al.
Published: (2024)

Pairwise sequence alignment with block and character edit operations
by: Alıcıoğlu, Ahmet Cemal, et al.
Published: (2023)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
by: Goranci, Gramoz, et al.
Published: (2025)

Combinatorial Stationary Prophet Inequalities
by: Patel, Neel, et al.
Published: (2023)

Fair Committee Selection under Ordinal Preferences and Limited Cardinal Information
by: Gadekar, Ameet, et al.
Published: (2025)

History-Independent Load Balancing
by: Bender, Michael A., et al.
Published: (2026)

Pandora with Inaccurate Priors
by: Banihashem, Kiarash, et al.
Published: (2025)

A Tolerant Independent Set Tester
by: Seth, Cameron
Published: (2025)

Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
by: Dughmi, Shaddin, et al.
Published: (2026)

Optimal Neighborhood Exploration for Dynamic Independent Sets
by: Borowitz, Jannick, et al.
Published: (2024)

Improved Certificates for Independence Number in Semirandom Hypergraphs
by: Kothari, Pravesh, et al.
Published: (2026)

On Computing Pairwise Statistics with Local Differential Privacy
by: Ghazi, Badih, et al.
Published: (2024)

Optimal Stopping with a Predicted Prior
by: Bai, Tian, et al.
Published: (2025)

The Distortion of Prior-Independent b-Matching Mechanisms
by: Caragiannis, Ioannis, et al.
Published: (2026)

Online Prediction with Limited Selectivity
by: Liu, Licheng, et al.
Published: (2025)

Finding Shortest Reconfiguration Sequences on Independent Set Polytopes
by: Cardinal, Jean, et al.
Published: (2026)

Sublinear Metric Steiner Forest via Maximal Independent Set
by: Mahabadi, Sepideh, et al.
Published: (2025)

Finding Triangles or Independent Sets; and Other Dual Pair Approximations
by: Dumitrescu, Adrian
Published: (2021)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
by: Bieliński, Paweł Rafał, et al.
Published: (2026)

Independence-Number Parameterized Space Complexity for Directed Connectivity Certificate
by: Chen, Ho-Lin, et al.
Published: (2026)

Data Reductions for the Strong Maximum Independent Set Problem in Hypergraphs
by: Großmann, Ernestine, et al.
Published: (2026)

Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
by: Conte, Alessio, et al.
Published: (2024)

Stochastic Embedding of Digraphs into DAGs
by: Filtser, Arnold
Published: (2025)

Sum-of-Squares Lower Bounds for Independent Set in Ultra-Sparse Random Graphs
by: Kothari, Pravesh, et al.
Published: (2024)

Almost-Uniform Edge Sampling: Leveraging Independent-Set and Local Graph Queries
by: Adar, Tomer, et al.
Published: (2026)

On the Approximability of Max-Cut on 3-Colorable Graphs and Graphs with Large Independent Sets
by: Ghoshal, Suprovat, et al.
Published: (2026)

Quantization for Vector Search under Streaming Updates
by: Aden-Ali, Ishaq, et al.
Published: (2025)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
by: Nadimpalli, Shivam, et al.
Published: (2024)

An Optimal Algorithm for Stochastic Vertex Cover
by: Brand, Jan van den, et al.
Published: (2026)

Scheduling on a Stochastic Number of Machines
by: Buchem, Moritz, et al.
Published: (2024)

Graph Partitioning With Limited Moves
by: Behbahani, Majid, et al.
Published: (2024)

A Comprehensive Survey of Data Reduction Rules for the Maximum Weighted Independent Set Problem
by: Großmann, Ernestine, et al.
Published: (2024)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
by: Eiben, Eduard, et al.
Published: (2024)

Classes Testable with $O(1/ε)$ Queries for Small $ε$ Independent of the Number of Variables
by: Bshouty, Nader H., et al.
Published: (2026)

Solution Discovery for Vertex Cover, Independent Set, Dominating Set, and Feedback Vertex Set
by: Saito, Rin, et al.
Published: (2025)

When Local and Non-Local Meet: Quadratic Improvement for Edge Estimation with Independent Set Queries
by: Adar, Tomer, et al.
Published: (2026)