More Like this

1. Reduction with Respect to the Effective Order and a New Type of Dimension Polynomials of Difference Modules

   https://doi.org/10.1145/3476446.3535497  

   Levin, Alexander (July 2022, 2022 International Symposium on Symbolic and Algebraic Computation)

   General Chair: Marc Moreno Chair: Lihong Zhi (Ed.)

   We introduce a new type of reduction in a free difference module over a difference field that uses a generalization of the concept of effective order of a difference polynomial. Then we define the concept of a generalized characteristic set of such a module, establish some properties of these characteristic sets and use them to prove the existence, outline a method of computation and find invariants of a dimension polynomial in two variables associated with a finitely generated difference module. As a consequence of these results, we obtain a new type of bivariate dimension polynomials of finitely generated difference field extensions. We also explain the relationship between these dimension polynomials and the concept of Einstein’s strength of a system of difference equations. 

   more » « less
2. Turaco: Complexity-Guided Data Sampling for Training Neural Surrogates of Programs

   https://doi.org/10.1145/3622856  

   Renda, Alex; Ding, Yi; Carbin, Michael (October 2023, Proceedings of the ACM on Programming Languages)

   Programmers and researchers are increasingly developing surrogates of programs, models of a subset of the observable behavior of a given program, to solve a variety of software development challenges. Programmers train surrogates from measurements of the behavior of a program on a dataset of input examples. A key challenge of surrogate construction is determining what training data to use to train a surrogate of a given program. We present a methodology for sampling datasets to train neural-network-based surrogates of programs. We first characterize the proportion of data to sample from each region of a program's input space (corresponding to different execution paths of the program) based on the complexity of learning a surrogate of the corresponding execution path. We next provide a program analysis to determine the complexity of different paths in a program. We evaluate these results on a range of real-world programs, demonstrating that complexity-guided sampling results in empirical improvements in accuracy. 

   more » « less
3. Fast Algorithms for Rank-1 Bimatrix Games

   https://doi.org/10.1287/opre.2020.1981  

   Adsul, Bharat; Garg, Jugal; Mehta, Ruta; Sohoni, Milind; von Stengel, Bernhard (March 2021, Operations Research)

   The rank of a bimatrix game is the matrix rank of the sum of the two payoff matrices. This paper comprehensively analyzes games of rank one and shows the following: (1) For a game of rank r, the set of its Nash equilibria is the intersection of a generically one-dimensional set of equilibria of parameterized games of rank r − 1 with a hyperplane. (2) One equilibrium of a rank-1 game can be found in polynomial time. (3) All equilibria of a rank-1 game can be found by following a piecewise linear path. In contrast, such a path-following method finds only one equilibrium of a bimatrix game. (4) The number of equilibria of a rank-1 game may be exponential. (5) There is a homeomorphism between the space of bimatrix games and their equilibrium correspondence that preserves rank. It is a variation of the homeomorphism used for the concept of strategic stability of an equilibrium component. 

   more » « less
4. Packing Geometric Objects with Optimal Worst-Case Density

   Becker, Aaron T.; Fekete, Sándor P.; Keldenich, Phillip; Morr, Sebastian; Scheffer, Christian (June 2019, International Symposium on Computational Geometry (SoCG))

   We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of different-size circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density δ∗ is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (δ∗ = 0.5), of circles in a square (δ∗ = 0.5390 . . .), regular octagons in a square (δ∗ = 0.5685 . . .), and circles in a circle (δ∗ = 0.5). 2012 ACM Subject Classification Theory of computation → Packing and covering problems; Theory of computation → Computational geometry 

   more » « less
5. Induced subgraphs and tree decompositions XIV. Non-adjacent neighbours in a hole

   https://doi.org/10.1016/j.ejc.2024.104074  

   Chudnovsky, Maria; Hajebi, Sepehr; Spirkl, Sophie (February 2025, European Journal of Combinatorics)

   A clock is a graph consisting of an induced cycle and a vertex not in with at least two non-adjacent neighbours in . We show that every clock-free graph of large treewidth contains a “basic obstruction” of large treewidth as an induced subgraph: a complete graph, a subdivision of a wall, or the line graph of a subdivision of a wall. 

   more » « less