[图书][B] Positional games
This monograph is an outcome of the Oberwolfach Seminar on Positional Games, given by
the authors at the Mathematisches Forschungsinstitut Oberwolfach (MFO) in Oberwolfach …
the authors at the Mathematisches Forschungsinstitut Oberwolfach (MFO) in Oberwolfach …
On simplified NP-complete variants of Monotone 3-Sat
We consider simplified versions of 3-Sat, the variant of the famous Satisfiability Problem
where each clause is made up of exactly three distinct literals formed over pairwise distinct …
where each clause is made up of exactly three distinct literals formed over pairwise distinct …
The local lemma is asymptotically tight for SAT
H Gebauer, T Szabó, G Tardos - Journal of the ACM (JACM), 2016 - dl.acm.org
The Local Lemma is a fundamental tool of probabilistic combinatorics and theoretical
computer science, yet there are hardly any natural problems known where it provides an …
computer science, yet there are hardly any natural problems known where it provides an …
A general framework for hypergraph coloring
IM Wanless, DR Wood - SIAM Journal on Discrete Mathematics, 2022 - SIAM
The Lovász Local Lemma is a powerful probabilistic technique for proving the existence of
combinatorial objects. It is especially useful for coloring graphs and hypergraphs with …
combinatorial objects. It is especially useful for coloring graphs and hypergraphs with …
A quantum Lovász local lemma
The Lovász Local Lemma (LLL) is a powerful tool in probability theory to show the existence
of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We …
of combinatorial objects meeting a prescribed collection of “weakly dependent” criteria. We …
The Lovász local lemma–a survey
M Szegedy - International Computer Science Symposium in Russia, 2013 - Springer
LNCS 7913 - The Lovász Local Lemma – A Survey Page 1 The Lovász Local Lemma – A
Survey Mario Szegedy⋆ Rutgers University, Piscataway NJ, USA Abstract. The Local Lemma of …
Survey Mario Szegedy⋆ Rutgers University, Piscataway NJ, USA Abstract. The Local Lemma of …
Sampling and the complexity of nature
D Hangleiter - arXiv preprint arXiv:2012.07905, 2020 - arxiv.org
Randomness is an intrinsic feature of quantum theory. The outcome of any quantum
measurement will be random, sampled from a probability distribution that is defined by the …
measurement will be random, sampled from a probability distribution that is defined by the …
Generalized query by transduction for online active learning
V Balasubramanian, S Chakraborty… - 2009 IEEE 12th …, 2009 - ieeexplore.ieee.org
Transductive inference has gained popularity in recent years as a means to develop pattern
classification approaches that address the specific issue of predicting the class label of a …
classification approaches that address the specific issue of predicting the class label of a …
Moser-Tardos Algorithm: Beyond Shearer's Bound
In a seminal paper (Moser and Tardos, JACM'10), Moser and Tardos developed a simple
and powerful algorithm to find solutions to constraint satisfaction problems. Kolipaka and …
and powerful algorithm to find solutions to constraint satisfaction problems. Kolipaka and …
Variable-version Lovász local lemma: Beyond Shearer's bound
A tight criterion under which the abstract version Lovász Local Lemma (abstract-LLL) holds
was given by Shearer [41] decades ago. However, little is known about that of the variable …
was given by Shearer [41] decades ago. However, little is known about that of the variable …