12 citations · 21 across the 9 of their papers we have counts for
14 papers
A cyclotomic gluing construction for lattice sphere packings
Nihar Gargava, Matthias Gröbner, Michael Simkin
For a positive integer , let denote the supremum of the densities of lattice sphere packings in . We prove that, for every sufficiently large , $Δ_d^L \g…
Non-existence probabilities and lower tails in the critical regime via Belief Propagation
Matthew Jenssen, Will Perkins, Aditya Potukuchi +1
We compute the logarithmic asymptotics of the non-existence probability (and more generally the lower-tail probability) for a wide variety of combinatorial problems for a range of…
A Toolkit for Robust Thresholds
Huy Tuan Pham, Ashwin Sah, Mehtaab Sawhney +1
Consider a host hypergraph which contains a spanning structure due to minimum degree considerations. We collect three results proving that if the edges of are sampled at th…
Threshold for Steiner triple systems
Ashwin Sah, Mehtaab Sawhney, Michael Simkin
We prove that with high probability contains a spanning Steiner triple system for , establishing the exponent for the thresho…
Substructures in Latin squares
Matthew Kwan, Ashwin Sah, Mehtaab Sawhney +1
We prove several results about substructures in Latin squares. First, we explain how to adapt our recent work on high-girth Steiner triple systems to the setting of Latin squares,…
High-Girth Steiner Triple Systems
Matthew Kwan, Ashwin Sah, Mehtaab Sawhney +1
We prove a 1973 conjecture due to Erdős on the existence of Steiner triple systems with arbitrarily high girth.
What is Learned in Knowledge Graph Embeddings?
Michael R. Douglas, Michael Simkin, Omri Ben-Eliezer +4
A knowledge graph (KG) is a data structure which represents entities and relations as the vertices and edges of a directed graph with edge types. KGs are an important primitive in…
The number of -queens configurations
Michael Simkin
The -queens problem is to determine , the number of ways to place mutually non-threatening queens on an board. We show that there exists a const…
A lower bound for the -queens problem
Zur Luria, Michael Simkin
The -queens puzzle is to place mutually non-attacking queens on an chessboard. We present a simple two stage randomized algorithm to construct such configuratio…
A randomized construction of high girth regular graphs
Nati Linial, Michael Simkin
We describe a new random greedy algorithm for generating regular graphs of high girth: Let and be fixed. Let be even and set $g = c \log_…
Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs
Roman Glebov, Zur Luria, Michael Simkin
Consider the random process in which the edges of a graph are added one by one in a random order. A classical result states that if is the complete graph or the co…
-Steiner Systems in Random Hypergraphs
Michael Simkin
Let be a random -uniform -vertex hypergraph where every -tuple belongs to independently with probability . We show that for some , if $p \geq…
On the Threshold Problem for Latin Boxes
Zur Luria, Michael Simkin
Let . An 0-1 array is a Latin box if it contains exactly ones, and has at most one in each line. As a special case, Latin boxes in w…
Monotone Subsequences in High-Dimensional Permutations
Nathan Linial, Michael Simkin
This paper is part of the ongoing effort to study high-dimensional permutations. We prove the analogue to the Erdős-Szekeres theorem: For every , every order- -dimensi…