Výsledky vyhledávání - "Mihir Singhal"

Tetris is NP-hard even with O(1) Rows or Columns

Autor: Adam Hesterberg, Michael J. Coulombe, Erik D. Demaine, Mihir Singhal, Jayson Lynch, Sualeh Asif, Martin L. Demaine

Publikováno v: Journal of Information Processing. 28:942-958

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 problems posed over 15 years ago [BDH+04]. Our reduction is from 3-Partiti

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_________::1c4412e4dae7dde8328c9c59c6088779
https://doi.org/10.2197/ipsjjip.28.942

Zobrazit plný text záznamu

Families with no perfect matchings

Autor: 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 $\mathcal{F}$ to have no perfect matching is for there to be a blocking set, which is a set

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::5acd278a010b76fed84dc9d666131a7a
http://arxiv.org/abs/2008.08792

Zobrazit plný text záznamu

Lower bounds for superpatterns and universal sequences

Autor: Zachary Chroman, Matthew Kwan, Mihir Singhal

A permutation $\sigma\in S_n$ is said to be $k$-universal or a $k$-superpattern if for every $\pi\in S_k$, there is a subsequence of $\sigma$ that is order-isomorphic to $\pi$. A simple counting argument shows that $\sigma$ can be a $k$-superpattern

Externí odkaz: https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0ed7db5c198d31280204c0d9c31677d4
http://arxiv.org/abs/2004.02375

Zobrazit plný text záznamu