Jeffery Li

MIT Hardness Group, Josh Brunner, Erik D. Demaine et al. · mit

We analyze the computational complexity of Tetris clearing (determining whether the player can clear an initial board using a given sequence of pieces) and survival (determining whether the player can avoid losing before placing all the given pieces in an initial board) when restricted to a single polyomino piece type. We prove, for any tetromino piece type $P$ except for O, the NP-hardness of Tetris clearing and survival under the standard Super Rotation System (SRS), even when the input sequence consists of only a specified number of $P$ pieces. These surprising results disprove a 23-year-old conjecture on the computational complexity of Tetris with only I pieces (although our result is only for a specific rotation system). As a corollary, we prove the NP-hardness of Tetris clearing when the sequence of pieces has to be able to be generated from a $7k$-bag randomizer for any positive integer $k\geq 1$. On the positive side, we give polynomial-time algorithms for Tetris clearing and survival when the input sequence consists of only dominoes, assuming a particular rotation model, solving a version of a 9-year-old open problem. Along the way, we give polynomial-time algorithms for Tetris clearing and survival with $1\times k$ pieces (for any fixed $k$), provided the top $k-1$ rows are initially empty, showing that our I NP-hardness result needs to have filled cells in the top three rows.

Long Phan, Alice Gatti, Ziwen Han et al. · amazon-science, apple-ml

Benchmarks are important tools for tracking the rapid advancements in large language model (LLM) capabilities. However, benchmarks are not keeping pace in difficulty: LLMs now achieve over 90\% accuracy on popular benchmarks like MMLU, limiting informed measurement of state-of-the-art LLM capabilities. In response, we introduce Humanity's Last Exam (HLE), a multi-modal benchmark at the frontier of human knowledge, designed to be the final closed-ended academic benchmark of its kind with broad subject coverage. HLE consists of 2,500 questions across dozens of subjects, including mathematics, humanities, and the natural sciences. HLE is developed globally by subject-matter experts and consists of multiple-choice and short-answer questions suitable for automated grading. Each question has a known solution that is unambiguous and easily verifiable, but cannot be quickly answered via internet retrieval. State-of-the-art LLMs demonstrate low accuracy and calibration on HLE, highlighting a significant gap between current LLM capabilities and the expert human frontier on closed-ended academic questions. To inform research and policymaking upon a clear understanding of model capabilities, we publicly release HLE at https://lastexam.ai.

Jeffery Li, Jayson Lynch, Liva Olina et al.

In nearly every discipline, scientific computations are limited by the cost and speed of computation. For example, the best-known exact algorithms for the canonical Traveling Salesman Problem would take centuries to run on an instance of size 1 million. A natural response to such limits is to try to find new algorithms or to parallelize existing ones, but many algorithms are already at their theoretically-optimal level and parallelization is often impossible or prohibitively expensive. Starting in the 1960's, computer scientists pursued another solution: allowing solutions to have a small amount of error (i.e. approximating them). In this paper, we survey 118 of the most important algorithm problems in computer science, quantifying the gains and tradeoffs from approximation that have been discovered over the history of the field. Overall, only $\approx$20\% of problems have benefited from approximation. However, those with good approximate algorithms can be dramatically faster to compute with little cost to accuracy. For example, a quarter of computationally intractable problems (e.g. those that take exponential time to compute) have polynomial time approximate algorithms. Approximation also increases the number of algorithms that can run in linear time by 23\%, opening up new computational opportunities for those working in the big data regime. This work also sheds light on what should be expected from progress in AI, where approximation is at the heart of how deep learning works.