M. Singhal

activity

20192022

most citedLow-Degree Multicalibration

2 citations · 4 across the 5 of their papers we have counts for

collaborators

Showing 2020Show all

4 papers · 1 filter

cs.CC2020

Tetris is NP-hard even with $O (1)$ rows or columns

Sualeh Asif, Michael Coulombe, Erik D. Demaine +4

We prove that the classic falling-block video game Tetris (both survival and board clearing) remains NP-complete even when restricted to 8 columns, or to 4 rows, settling open prob…

math.CO2020

Families with no perfect matchings

Mihir Singhal

We consider families of $k$ -subsets of ${1, \dots, n}$ , where $n$ is a multiple of $k$ , which have no perfect matching. An equivalent condition for a family $F$ to have…

math.CO2020

Unimodality of a refinement of Lassalle's sequence

Mihir Singhal

Defant, Engen, and Miller defined a refinement of Lassalle's sequence $A_{k + 1}$ by considering uniquely sorted permutations of length $2 k + 1$ whose first element is $ℓ$ . They sho…

math.CO2020

Lower bounds for superpatterns and universal sequences

Zachary Chroman, Matthew Kwan, Mihir Singhal

A permutation $σ \in S_{n}$ is said to be $k$ -universal or a $k$ -superpattern if for every $π \in S_{k}$ , there is a subsequence of $σ$ that is order-isomorphic to $π$ . A simple counting…

Tetris is NP-hard even with O(1) rows or columns

Families with no perfect matchings

Unimodality of a refinement of Lassalle's sequence

Lower bounds for superpatterns and universal sequences

Tetris is NP-hard even with $O (1)$ rows or columns