4 citations · 6 across the 3 of their papers we have counts for
5 papers
Regarding two conjectures on clique and biclique partitions
Dhruv Rohatgi, John C. Urschel, Jake Wellens
For a graph , let denote the minimum number of cliques of needed to cover the edges of exactly once. Similarly, let denote the minimum number of bicliq…
Testing Gap k-planarity is NP-complete
John C. Urschel, Jake Wellens
For all , we show that deciding whether a graph is -planar is NP-complete, extending the well-known fact that deciding 1-planarity is NP-complete. Furthermore, we show…
A tighter bound on the number of relevant variables in a bounded degree Boolean function
Jake Wellens
A classical theorem of Nisan and Szegedy says that a boolean function with degree as a real polynomial depends on at most of its variables. In recent work by Chiarel…
A note on partial rejection sampling for the hard disks model in the plane
Jake Wellens
In this note, we slightly improve the guarantees obtained by Guo and Jerrum for sampling from the hard disks model in the plane via partial rejection sampling. Our proof makes use…
On Graphs and the Gotsman-Linial Conjecture for d = 2
Hyo Won Kim, Chris Maldonado, Jake Wellens
We give an infinite class of counterexamples to the Gotsman-Linial conjecture when d = 2. On the other hand, we establish an asymptotic form of the conjecture for quadratic thresho…