☆ 4.2 Article

Deterministic algorithms for the Lovasz local lemma: Simpler, more general, and more parallel

RANDOM STRUCTURES & ALGORITHMS (2023)

相关参考文献

注意：仅列出部分参考文献，下载原文获取全部文献信息。

Article Computer Science, Theory & Methods

Algorithms for Weighted Independent Transversals and Strong Colouring

Alessandra Graf et al.

Summary: This article presents a new randomized algorithm that is more widely applicable and efficient in solving problems related to the strong chromatic number of graphs, closing the gap between existing bounds and algorithmic proofs.

ACM TRANSACTIONS ON ALGORITHMS (2022)

添加到收藏夹

Article Computer Science, Theory & Methods

Oblivious Resampling Oracles and Parallel Algorithms for the Lopsided Lovasz Local Lemma

David G. Harris

Summary: The Lovasz Local Lemma (LLL) states that it is possible for a collection of unlikely and relatively independent bad events to not occur simultaneously in a probability space. Moser and Tardos (2010) introduced algorithms that efficiently transform applications of the LLL. A framework by Harvey and Vondrak (2015) extended this to other probability spaces by using resampling oracles, leading to sequential algorithms based on a generalization of the LLL known as the Lopsided Lovasz Local Lemma (LLLL).

ACM TRANSACTIONS ON ALGORITHMS (2021)

添加到收藏夹

Article Computer Science, Software Engineering

New bounds for the Moser-Tardos distribution

David G. Harris

RANDOM STRUCTURES & ALGORITHMS (2020)

添加到收藏夹

Article Computer Science, Theory & Methods

Finding independent transversals efficiently

Alessandra Graf et al.

COMBINATORICS PROBABILITY & COMPUTING (2020)

添加到收藏夹

Article Computer Science, Software Engineering

Deterministic Parallel Algorithms for Bilinear Objective Functions

David G. Harris

ALGORITHMICA (2019)

添加到收藏夹

Article Computer Science, Theory & Methods

Deterministic Parallel Algorithms for Fooling Polylogarithmic Juntas and the Lovasz Local Lemma

David G. Harris

ACM TRANSACTIONS ON ALGORITHMS (2018)

添加到收藏夹

Article Computer Science, Theory & Methods

Parallel Algorithms and Concentration Bounds for the Lovasz Local Lemma via Witness DAGs

Bernhard Haeupler et al.

ACM TRANSACTIONS ON ALGORITHMS (2017)

添加到收藏夹

Article Computer Science, Hardware & Architecture

The Local Lemma Is Asymptotically Tight for SAT

Heidi Gebauer et al.

JOURNAL OF THE ACM (2016)

添加到收藏夹

Proceedings Paper Computer Science, Theory & Methods

An Algorithmic Proof of the Lovasz Local Lemma via Resampling Oracles

Nicholas J. A. Harvey et al.

2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (2015)

添加到收藏夹

Article Computer Science, Theory & Methods

DETERMINISTIC ALGORITHMS FOR THE LOVASZ LOCAL LEMMA

Karthekeyan Chandrasekaran et al.

SIAM JOURNAL ON COMPUTING (2013)

添加到收藏夹

Article Computer Science, Theory & Methods

An Improvement of the Lovasz Local Lemma via Cluster Expansion

Rodrigo Bissacot et al.

COMBINATORICS PROBABILITY & COMPUTING (2011)

添加到收藏夹

Article Computer Science, Hardware & Architecture

New Constructive Aspects of the Lovasz Local Lemma

Bernhard Haeupler et al.

JOURNAL OF THE ACM (2011)

添加到收藏夹

Article Computer Science, Hardware & Architecture

A Constructive Proof of the General Lovasz Local Lemma

Robin A. Moser et al.

JOURNAL OF THE ACM (2010)

添加到收藏夹

Article Mathematics

An improved bound for the strong chromatic number

P. E. Haxell

JOURNAL OF GRAPH THEORY (2008)

添加到收藏夹

Article Mathematics

Independent systems of representatives in weighted graphs

Ron Aharoni et al.

COMBINATORICA (2007)

添加到收藏夹

Article Mathematics

Extremal problems for transversals in graphs with bounded degree

Tibor Szabo et al.

COMBINATORICA (2006)

添加到收藏夹

Article Computer Science, Software Engineering

Nonrepetitive colorings of graphs

N Alon et al.

RANDOM STRUCTURES & ALGORITHMS (2002)

添加到收藏夹

Article Computer Science, Software Engineering

Solving some discrepancy problems in NC

S Mahajan et al.

ALGORITHMICA (2001)

添加到收藏夹

© Peeref 2019-2024. All rights reserved.