BARC PhD receives Best Student Paper Award at STOC'26

Computational geometry studies computational problems that involve geometric shapes like points, lines, and polygons. A classic example is the art-gallery problem. Given the floor plan of an art gallery, we want to choose some locations to place guards. The guards need to be able to see everything in the art gallery (we don't want to leave any blind spots), but we also don't want to use too many guards. The art-gallery problem asks us to find the smallest possible set of guards so that nothing is left unguarded. 

A common challenge in the study of computational geometry is that computers can't easily represent arbitrary real numbers. Often, researchers will try to show that we can solve problems using "nice" coordinates like integers or rational numbers, which are straightforward to represent on a computer. But this isn't always possible. For example, there are instances of the art-gallery problem where an optimal solution requires a guard to be placed at a position that is a distance of √2 from one of the walls of the art gallery, even if the art-gallery itself can be described with rational numbers.

An irrational number like √2 is certainly harder to compute with compared to a rational number, but it could be much worse. We say that a real number can be written in terms of radicals if can be expressed using integers, addition, subtraction, multiplication, division, and nth root symbols. Galois theory says that there are polynomial equations like x^5=1+x that have real solutions, but none that can be written in terms of radicals. In fact, it is possible to construct art-galleries that need this type of number in their solution. We might not even be able to express an optimal solution in terms of radicals!

It seems like there is little hope of being able to efficiently solve the art-gallery problem. An optimal solution might even be too complicated to write down. But maybe some other variant of the problem could be easier. 

For example, in many art-galleries, the valuable art is affixed to the walls of the gallery. So while the guards should be able to see all the art, it might be ok if there are some blind spots in the middle of a room. Also, the guards shouldn't obstruct the flow of visitors through the gallery, so we can ask for each guard location to be placed against the wall (and not somewhere in the middle of the room). These two modifications define a variant of the art-gallery problem called the boundary-boundary variant. The name boundary-boundary refers to the fact that only the boundary (that is, the walls of the art gallery) needs to be guarded, and the guards need to be placed on the boundary. 

Researchers originally hoped that they could solve the boundary-boundary variant using only rational coordinates. Stade shows that this isn't true. He gives a construction of an art-gallery whose boundary can be guarded with 3 boundary guards, but only if we allow irrational coordinates like √2 for the guard positions. The construction, along with the optimal guarding configuration, is illustrated below.

 

However, unlike the general art-gallery problem, Stade also shows that optimal solutions can at least always be written in terms of radicals. In order to show this, Stade used ideas about constraint satisfaction problems. A constraint satisfaction problem is a type of problem where we have some variables and constraints, and we want to find an assignment of variables that satisfies the constraints. For example, Sudoku is a constraint satisfaction problem where each variable is a positive integer less than 10, and there are constraints that numbers can't repeat in a row, column, or box.

A constraint satisfaction problem also defines a domain for the variables. For example, in Sudoku, the variables must be a positive integer less than 10. We can't use integers outside this range like 0 or 10, and we can't use fractions or irrational numbers like 3/2 or √2. Often, the domain is a finite set. But there are also continuous constraint satisfaction problems where the variables can be arbitrary real numbers.

Constraint satisfaction problems show up almost everywhere in computer science, but in general they are very difficult to solve. For example, there is no easy process that can solve every sudoku. Solvers of difficult Sudokus use many different techniques to rule out certain possibilities, until eventually they can find the solution. It isn't always easy to spot the right technique, and it often requires creativity in order to come up the idea that leads to a solution. 

However, there are many known techniques that can help solve certain restricted classes of constraint satisfaction problem. Stade notices that some of these techniques could almost be applied to the boundary-boundary art-gallery problem. The catch is that these techniques were previously only known to work for constraint satisfaction problems with variable in a finite domain, but Stade needed to generalize them to an infinite setting. The result is a proof that, while we might still need irrational coordinates like √2, there is always a solution where the coordinates can be written in terms of rational numbers and at most a single square-root symbol. This means that the problem can always be solved in terms of radicals. 

 

STOC, a leading conference in algorithms and complexity, will be held in Salt Lake City June 22-26. In addition to the paper by Jack Stade, the following papers co-authored by BARC researchers will  be presented:

Separator Theorem for Minor-Free Graphs in Linear Time. Édouard Bonnet, Tuukka Korhonen, Hung Le, Jason Li, and Tomáš Masařík.

Dynamic Meta-Kernelization. Christian Bertram, Deborah Haun, and Mads Vestergaard Jensen, Tuukka Korhonen.

Better neural network expressivity: subdividing the simplex. Egor Bakaev, Florestan Brunck, Christoph Hertrich, Jack Stade, Amir Yehudayoff.

Negations are powerful even in small depth. Bruno Pasqualotto Cavalar, T

héo Fabris, Partha Mukhopadhyay, Srikanth Srinivasan, Amir Yehudayoff.

Ideals, Gröbner Bases, and PCPs. Prashanth Amireddy, Amik Raj Behera, Srikanth Srinivasan, Madhu Sudan, Sophus Valentin Willumsgaard.

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials. Prateek Dwivedi, Benedikt Pago, Tim Seppelt.

Topics