Buchumschlag

Average-Case Matrix Discrepancy: Asymptotics and Online Algorithms

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kunisky, Dmitriy, Zhang, Peiyuan
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms Discrete Mathematics Combinatorics Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Asymptotic Bounds and Online Algorithms for Average-Case Matrix Discrepancy
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
von: Gamarnik, David, et al.
Veröffentlicht: (2026)

Strong spatial mixing for colorings on trees and its algorithmic applications
von: Chen, Zongchen, et al.
Veröffentlicht: (2023)

Boltzmann Sampling for Powersets without an Oracle
von: Peyen, Jean
Veröffentlicht: (2026)

Integrating High-Dimensional Functions Deterministically
von: Gamarnik, David, et al.
Veröffentlicht: (2024)

The Compilability Thresholds of 2-CNF to OBDD
von: de Colnet, Alexis, et al.
Veröffentlicht: (2026)

Cycle-factors of regular graphs via entropy
von: Christoph, Micha, et al.
Veröffentlicht: (2025)

Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
von: Bansal, Nikhil, et al.
Veröffentlicht: (2025)

Probabilistic estimates of the diameters of the Rubik's Cube groups
von: Hirata, So
Veröffentlicht: (2024)

Sharp Online Hardness for Large Balanced Independent Sets
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2025)

Constructive l2-Discrepancy Minimization with Additive Deviations
von: Dutta, Kunal
Veröffentlicht: (2025)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2026)

Non-Additive Discrepancy: Coverage Functions in a Beck-Fiala Setting
von: Avila, Tatiana Rocha, et al.
Veröffentlicht: (2026)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
von: Deák, Bence, et al.
Veröffentlicht: (2026)

Online Coloring of Short Intervals
von: Chybowska-Sokół, Joanna, et al.
Veröffentlicht: (2018)

Matrix Scaling: a New Heuristic for the Feedback Vertex Set Problem
von: Shook, James M., et al.
Veröffentlicht: (2025)

A Method for Generating Connected Erdos-Renyi Random Graphs
von: Chinyaev, Boris
Veröffentlicht: (2025)

The Squishy Grid Problem
von: Cai, Zixi, et al.
Veröffentlicht: (2025)

A Uniformly Random Solution to Algorithmic Redistricting
von: Cai, Jin-Yi, et al.
Veröffentlicht: (2024)

Stable Approximation Algorithms for Dominating Set and Independent Set
von: de Berg, Mark, et al.
Veröffentlicht: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
von: Dudeja, Aditi, et al.
Veröffentlicht: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
von: Bourneuf, Romain, et al.
Veröffentlicht: (2025)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
von: Iwata, Satoru, et al.
Veröffentlicht: (2024)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
von: Kita, Nanano
Veröffentlicht: (2025)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
von: Jana, Satyabrata, et al.
Veröffentlicht: (2025)

A Fast Algorithm for Finding Minimum Weight Cycles in Mining Cyclic Graph Topologies
von: Shakeri, Heman, et al.
Veröffentlicht: (2025)

Separating Feasibility and Movement in Solution Discovery: The Case of Path Discovery
von: von Bergen, Hanno, et al.
Veröffentlicht: (2026)

A Near-Linear-Time Algorithm for Finding a Well-Spread Perfect Matching in Bridgeless Cubic Graphs
von: Ghanbari, Babak, et al.
Veröffentlicht: (2026)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
von: Kunisky, Dmitriy
Veröffentlicht: (2024)

Faster Mixing of the Jerrum-Sinclair Chain
von: Chen, Xiaoyu, et al.
Veröffentlicht: (2025)

Sparsest cut and eigenvalue multiplicities on low degree Abelian Cayley graphs
von: d'Orsi, Tommaso, et al.
Veröffentlicht: (2024)

The Gap Between Greedy Algorithm and Minimum Multiplicative Spanner
von: Chen, Yeyuan
Veröffentlicht: (2024)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
von: Carlson, Charlie, et al.
Veröffentlicht: (2024)

Zero-free regions and concentration inequalities for hypergraph colorings in the local lemma regime
von: Liu, Jingcheng, et al.
Veröffentlicht: (2026)

A Tight Bound on Localization of Electrical Flows
von: Gurel-Gurevich, Ori, et al.
Veröffentlicht: (2026)

Sink-free orientations: a local sampler with applications
von: Anand, Konrad, et al.
Veröffentlicht: (2025)

Towards an Optimal Contention Resolution Scheme for Matchings
von: Nuti, Pranav, et al.
Veröffentlicht: (2022)