By Jin-Yi Cai and Zhiguo Fu
SIAM Journal on Computing, Ahead of Print.
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1)...

By Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
SIAM Journal on Computing, Ahead of Print.
For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad,...

By Danny Nguyen and Igor Pak
SIAM Journal on Computing, Ahead of Print.
We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by “short” we mean sentences with a bounded number...

By László Kozma and Thatchaphol Saranurak
SIAM Journal on Computing, Ahead of Print.
We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of...

By Dimitris Achlioptas, Fotis Iliopoulos, and Vladimir Kolmogorov
SIAM Journal on Computing, Volume 48, Issue 5, Page 1583-1602, January 2019.
We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms...

By Andrea Farruggia, Paolo Ferragina, Antonio Frangioni, and Rossano Venturini
SIAM Journal on Computing, Volume 48, Issue 5, Page 1603-1642, January 2019.
Since the seminal work by Shannon, theoreticians have focused on designing compressors targeted at minimizing the output...

By Sam Mattheus
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2126-2139, January 2019.
The notion of digits in finite fields was introduced a few years ago as an attempt...

By Klaus Jansen and Kim-Manuel Klein
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2062-2091, January 2019.
In this paper we develop new techniques for covering linear programs and covering integer linear programs...

By Elena Grigorescu, Akash Kumar, and Karl Wimmer
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2111-2125, January 2019.
A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it flips between 0 and...

By Benjamin Burton, Sergio Cabello, Stefan Kratsch, and William Pettersson
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2092-2110, January 2019.
We consider the problem of finding a subcomplex $\mathcal{K}'$ of a simplicial complex $\mathcal{K}$ such that...

By Elaine Levey and Thomas Rothvoss
SIAM Journal on Computing, Ahead of Print.
In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and the goal is to find...

By Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg
SIAM Journal on Computing, Ahead of Print.
We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai, Daskalakis, and Weinberg...

By Stephen Fenner, Rohit Gurjar, and Thomas Thierauf
SIAM Journal on Computing, Ahead of Print.
We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$,...

By Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum
SIAM Journal on Computing, Ahead of Print.
The celebrated ${\sf IP}={\sf PSPACE}$ theorem [Lund, Fortnow, Karloff, and Nisan, J. ACM, 39 (1992), pp. 859--868; Shamir, J. ACM, 39 (1992),...

By Anat Ganor, Gillat Kol, and Ran Raz
SIAM Journal on Computing, Ahead of Print.
We show an exponential gap between communication complexity and external information complexity by analyzing a communication task suggested as a candidate by...

By Jin-Yi Cai and Zhiguo Fu
SIAM Journal on Computing, Ahead of Print.
We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1)...

By Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr Sankowski
SIAM Journal on Computing, Ahead of Print.
For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad,...

By Danny Nguyen and Igor Pak
SIAM Journal on Computing, Ahead of Print.
We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by “short” we mean sentences with a bounded number...

By László Kozma and Thatchaphol Saranurak
SIAM Journal on Computing, Ahead of Print.
We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of...

By Dimitris Achlioptas, Fotis Iliopoulos, and Vladimir Kolmogorov
SIAM Journal on Computing, Volume 48, Issue 5, Page 1583-1602, January 2019.
We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These algorithms...

By Andrea Farruggia, Paolo Ferragina, Antonio Frangioni, and Rossano Venturini
SIAM Journal on Computing, Volume 48, Issue 5, Page 1603-1642, January 2019.
Since the seminal work by Shannon, theoreticians have focused on designing compressors targeted at minimizing the output...

By Sam Mattheus
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2126-2139, January 2019.
The notion of digits in finite fields was introduced a few years ago as an attempt...

By Klaus Jansen and Kim-Manuel Klein
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2062-2091, January 2019.
In this paper we develop new techniques for covering linear programs and covering integer linear programs...

By Elena Grigorescu, Akash Kumar, and Karl Wimmer
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2111-2125, January 2019.
A function $f:\{0,1\}^n\rightarrow \{0,1\}$ is said to be $k$-monotone if it flips between 0 and...

By Benjamin Burton, Sergio Cabello, Stefan Kratsch, and William Pettersson
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2092-2110, January 2019.
We consider the problem of finding a subcomplex $\mathcal{K}'$ of a simplicial complex $\mathcal{K}$ such that...

By Elaine Levey and Thomas Rothvoss
SIAM Journal on Computing, Ahead of Print.
In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and the goal is to find...

By Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg
SIAM Journal on Computing, Ahead of Print.
We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai, Daskalakis, and Weinberg...

By Stephen Fenner, Rohit Gurjar, and Thomas Thierauf
SIAM Journal on Computing, Ahead of Print.
We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$,...

By Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum
SIAM Journal on Computing, Ahead of Print.
The celebrated ${\sf IP}={\sf PSPACE}$ theorem [Lund, Fortnow, Karloff, and Nisan, J. ACM, 39 (1992), pp. 859--868; Shamir, J. ACM, 39 (1992),...

By Anat Ganor, Gillat Kol, and Ran Raz
SIAM Journal on Computing, Ahead of Print.
We show an exponential gap between communication complexity and external information complexity by analyzing a communication task suggested as a candidate by...

By Nikhil Bansal, Aravind Srinivasan, and Ola Svensson
SIAM Journal on Computing, Ahead of Print.
We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our...

By George Christodoulou, Martin Gairing, Yiannis Giannakopoulos, and Paul G. Spirakis
SIAM Journal on Computing, Volume 48, Issue 5, Page 1544-1582, January 2019.
We give exponential lower bounds on the Price of Stability (PoS) of weighted congestion games with polynomial...

By Sepehr Assadi, Sanjeev Khanna, and Yang Li
SIAM Journal on Computing, Ahead of Print.
We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover...

By Joseph Hyde, Hong Liu, and Andrew Treglown
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2041-2061, January 2019.
An important result of Komlós [Tiling Turán theorems, Combinatorica, 2000] yields the asymptotically exact minimum degree...

By Mark Bun and Justin Thaler
SIAM Journal on Computing, Ahead of Print.
The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial...

By Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin Ward
SIAM Journal on Computing, Ahead of Print.
Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any...

By Brett Hemenway, Noga Ron-Zewi, and Mary Wootters
SIAM Journal on Computing, Ahead of Print.
We show that the tensor product of a high-rate globally list recoverable code is (approximately) locally list recoverable. List recovery has been...

By Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini Vasudevan
SIAM Journal on Computing, Ahead of Print.
We examine the power of statistical zero knowledge proofs (captured by the complexity class $SZK$) and their variants. First, we give the...

By Lucas de Oliveira Contiero, Carlos Hoppen, Hanno Lefmann, and Knut Odermann
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2023-2040, January 2019.
Mubayi and Pikhurko established several Turán-type results and stability results for $r$-uniform hypergraphs. In particular, they...

By Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai
SIAM Journal on Computing, Ahead of Print.
We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted networks (the \sf CONGEST model);...

By Leqi Zhu
SIAM Journal on Computing, Ahead of Print.
In the consensus problem, there are $n$ processes that each has a private input value. Each nonfaulty process must output a single...

By Shaddin Dughmi and Haifeng Xu
SIAM Journal on Computing, Ahead of Print.
Persuasion, defined as the act of exploiting an informational advantage in order to influence the decisions of others, is ubiquitous. Indeed, persuasive...

By Shahar Dobzinski
SIAM Journal on Computing, Ahead of Print.
We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski,...

By Gil Cohen
SIAM Journal on Computing, Ahead of Print.
In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $(2+o(1))\log{n}$-Ramsey graphs on $n$ vertices. Matching Erdös's result...

By Tobias Harks, Anja Schedel, and Manuel Surek
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1932-1996, January 2019.
In a seminal paper, Chen, Roughgarden, and Valiant [SIAM J. Comput., 39 (5) (2010), pp. 1799--1832]...

By Guantao Chen and Songling Shan
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1997-2022, January 2019.
Let $G$ be an $n$-vertex graph with $n\ge 3$. A classic result of Dirac from 1952...

By Chidambaram Annamalai
SIAM Journal on Computing, Volume 48, Issue 5, Page 1503-1543, January 2019.
We study the restricted case of Scheduling on Unrelated Parallel Machines. In this problem, we are given...

By Daniel Lokshtanov, Saket Saurabh, Roohani Sharma, and Meirav Zehavi
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1878-1911, January 2019.
The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal...

By Roy Oursler and Andrzej Czygrinow
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1912-1931, January 2019.
Let $C^t$ denote the loose cycle on $t = 2s$ vertices, that is, the 3-uniform hypergraph...

By Michael A. Bekos, Henry Förster, Martin Gronemann, Tamara Mchedlidze, Fabrizio Montecchiani, Chrysanthi Raftopoulou, and Torsten Ueckerdt
SIAM Journal on Computing, Volume 48, Issue 5, Page 1487-1502, January 2019.
A queue layout of a graph consists of a linear order of its vertices and a partition...

By Kenta Ozeki, Atsuhiro Nakamoto, and Takayuki Nozawa
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1801-1836, January 2019.
For a positive integer $k$, a book (with $k$ pages) is a topological space consisting of...

By Alberto Espuny Díaz, Felix Joos, Daniela Kühn, and Deryk Osthus
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1837-1863, January 2019.
Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made...

By Thao Do
SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 1864-1877, January 2019.
The representation complexity of a bipartite graph $G=(P,Q)$ is the minimum size $\sum_{i=1}^s (|A_i|+|B_i|)$ over all...

By Eduard Eiben, Mithilesh Kumar, Amer E. Mouawad, Fahad Panolan, and Sebastian Siebertz
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1743-1771, January 2019.
For $\alpha > 1$, an $\alpha$-approximate (bi)kernel is a polynomial-time algorithm that takes as input an...

By Gweneth McKinley
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1772-1800, January 2019.
In the theory of dense graph limits, a graphon is a symmetric measurable function $W\colon[0,1]^2\to [0,1]$....

By Daniel I. Bernstein and Robert Krone
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1725-1742, January 2019.
The Cayley--Menger variety is the Zariski closure of the set of vectors specifying the pairwise squared...

By Yu Yokoi
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1712-1724, January 2019.
In some game-theoretic models, an agent is supposed to choose a subset of available items under...

By István Kovács and Daniel Soltész
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1691-1711, January 2019.
Two permutations $\pi_1,\pi_2$ of $[n]=\{1,2, \ldots, n\}$ are $k$-neighbor separated if there are two elements $a,b...

By Joshua Erde and Daniel Weißauer
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1654-1661, January 2019.
As a major step in their proof of Wagner's conjecture, Robertson and Seymour showed that every...

By Gérard Cohen, Emanuela Fachini, and János Körner
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1662-1668, January 2019.
We consider graphs whose vertex set is the set of permutations of the first $n$ natural...

By Domingos Dellamonica Jr and Vojtěch Rödl
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1669-1690, January 2019.
We prove that any Steiner triple system $\mathcal{S}$, with $n = v(\mathcal{S})$ sufficiently large, admits a...

By João Gouveia, Antonio Macchia, Rekha R. Thomas, and Amy Wiebe
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1637-1653, January 2019.
In this paper we introduce a natural model for the realization space of a polytope up...

By Steven Kelk and Simone Linz
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1556-1574, January 2019.
In 2001 Allen and Steel showed that, if subtree and chain reduction rules have been applied...

By Aaron Bernstein, Karl Däubel, Yann Disser, Max Klimm, Torsten Mütze, and Frieder Smolny
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1607-1636, January 2019.
Compression and sparsification algorithms are frequently applied in a preprocessing step before analyzing or optimizing large...

By Oded Schwartz and Elad Weiss
SIAM Journal on Computing, Volume 48, Issue 5, Page 1481-1486, January 2019.
The matrix chain ordering problem aims to reduce the number of arithmetic operations required for evaluating the...

By Peter Ayre and Catherine Greenhill
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1575-1606, January 2019.
We consider the problem of $q$-coloring a $k$-uniform random hypergraph, where $q,k \geq 3$, and determine...

By Guido Besomi, Matías Pavez-Signé, and Maya Stein
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1521-1555, January 2019.
We conjecture that every graph of minimum degree at least $\frac k2$ and maximum degree at...

By Michael Elkin and Ofer Neiman
SIAM Journal on Computing, Volume 48, Issue 4, Page 1436-1480, January 2019.
A $(\beta,\epsilon)$-hopset for a weighted undirected n-vertex graph $G=(V,E)$ is a set of edges, whose addition to...

By Guangyue Han
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1482-1502, January 2019.
Consider an acyclic directed graph $G$ with sources $s_1, s_2, \ldots,s_n$ and sinks $r_1, r_2, \ldots,...

By Louis DeBiasio and Allan Lo
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1503-1520, January 2019.
A branch vertex in a tree is a vertex of degree at least three. We prove...

By Zhiyang He and Michael Tait
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1472-1481, January 2019.
In this paper we study the maximum number of hyperedges which may be in an $r$-uniform...

By Yuichi Yoshida
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1452-1471, January 2019.
We consider the problem of maximizing a monotone submodular function under a knapsack constraint. We show...

By Naoyuki Kamiyama
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1431-1451, January 2019.
The Pareto stability is one of the solution concepts in two-sided matching markets with ties. It...

By Daniel Kane, Shachar Lovett, and Sankeerth Rao
SIAM Journal on Computing, Volume 48, Issue 4, Page 1425-1435, January 2019.
Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure...

By Heng Guo, Chao Liao, Pinyan Lu, and Chihao Zhang
SIAM Journal on Computing, Volume 48, Issue 4, Page 1397-1424, January 2019.
We give a fully polynomial-time approximation scheme (FPTAS) to count the number of $q$-colorings for $k$-uniform hypergraphs...

By George Christodoulou and Alkmini Sgouritsa
SIAM Journal on Computing, Volume 48, Issue 4, Page 1364-1396, January 2019.
We consider the problem of designing network cost-sharing protocols with good equilibria under uncertainty. The underlying game...

By John Gimbel, André Kündgen, Binlong Li, and Carsten Thomassen
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1415-1430, January 2019.
We study methods for finding strict upper bounds on the fractional chromatic number $\chi_f(G)$ of a...

By Atsuhiro Nakamoto, Kenta Noguchi, and Kenta Ozeki
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1390-1414, January 2019.
In order to attack some problems in computational geometry, Hoffmann and Kriegel [SIAM J. Discrete Math.,...

By Colin Cooper, Alan M. Frieze, and Wesley Pegden
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1374-1389, January 2019.
We consider arbitrary graphs $G$ with $n$ vertices and minimum degree at least $\delta n$ where...

By Naman Agarwal, Karthekeyan Chandrasekaran, Alexandra Kolla, and Vivek Madan
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1338-1373, January 2019.
A $k$-lift of an $n$-vertex base graph $G$ is a graph $H$ on $n\times k$ vertices,...

By Shiliang Gao and Shira Zerbib
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1326-1337, January 2019.
A family of sets satisfies the $(p,q)$ property if among every $p$ members of it some...

By Stephen D. Miller and Noah Stephens-Davidowitz
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1313-1325, January 2019.
We generalize Banaszczyk's seminal tail bound for the Gaussian mass of a lattice to a...

By Wei Dong and Baogang Xu
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1297-1312, January 2019.
A vertex coloring is said to be 2-distance if any two distinct vertices of...

By Surender Baswana, Shreejit Ray Chaudhury, Keerti Choudhary, and Shahbaz Khan
SIAM Journal on Computing, Volume 48, Issue 4, Page 1335-1363, January 2019.
Depth first search (DFS) tree is a fundamental data structure for solving various problems in graphs. It...

By Syed M. Meesum, Fahad Panolan, Saket Saurabh, and Meirav Zehavi
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1277-1296, January 2019.
The question of the existence of a polynomial kernelization of the Vertex Cover Above LP problem...

By Hendrik W. Lenstra and Alice Silverberg
SIAM Journal on Computing, Volume 48, Issue 4, Page 1300-1334, January 2019.
A CM-order is a reduced order equipped with an involution that mimics complex conjugation. The Witt--Picard group...

By József Balogh, Bernard Lidický, and Gelasio Salazar
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1261-1276, January 2019.
Borrowing László Székely's lively expression, we show that Hill's conjecture is “asymptotically at least $98.5\%$ true.”...

By Manuel Bodirsky, Barnaby Martin, Michael Pinsker, and András Pongrácz
SIAM Journal on Computing, Volume 48, Issue 4, Page 1224-1264, January 2019.
For $n\geq 3$, let $(H_n, E)$ denote the $n$th Henson graph, i.e., the unique countable homogeneous graph...

By Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, and Suresh Venkatasubramanian
SIAM Journal on Computing, Volume 48, Issue 4, Page 1265-1299, January 2019.
In the setting of streaming interactive proofs (SIPs), a client (verifier) needs to compute a given function...

By Wai-Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, and Debmalya Panigrahi
SIAM Journal on Computing, Volume 48, Issue 4, Page 1196-1223, January 2019.
We present a general framework for constructing cut sparsifiers in undirected graphs---weighted subgraphs for which every cut...

By Gilles Brassard, Ashwin Nayak, Alain Tapp, Dave Touchette, and Falk Unger
SIAM Journal on Computing, Volume 48, Issue 4, Page 1147-1195, January 2019.
We study the problem of simulating protocols in a quantum communication setting over noisy channels. This problem...

By Eimear Byrne and Alberto Ravagnani
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1242-1260, January 2019.
A $t$-$(n,d,\lambda)$ design over $\mathbb{F}_{q}$, or a subspace design, is a collection of $d$-dimensional subspaces of...

By Daniel W. Cranston and Landon Rabern
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1228-1241, January 2019.
A simple graph $G$ is overfull if ${|E(G)|}>\Delta\lfloor|V(G)|/2\rfloor$. By the pigeonhole principle, every overfull graph $G$...

By Andrzej Dudek, Sean English, and Alan M. Frieze
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1216-1227, January 2019.
The game of plates and olives was originally formulated by Nicolaescu and encodes the evolution of...

By Martin Dyer and Haiko Muller
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1146-1174, January 2019.
We examine the problem of exactly or approximately counting all perfect matchings in hereditary classes of...

By Martin Babka, Jan Bulánek, Vladimŕ Čunát, Michal Koucký, and Michael E. Saks
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1175-1193, January 2019.
In the online labeling problem with parameters $n$ and $m$ we are presented with a sequence...

By Daniel Lokshtanov, Amer E. Mouawad, Saket Saurabh, and Meirav Zehavi
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1194-1215, January 2019.
The Cycle Packing problem asks whether a given undirected graph $G=(V,E)$ contains $k$ vertex-disjoint cycles. Since...

By Yasushi Kawase, Hanna Sumita, and Takuro Fukunaga
SIAM Journal on Discrete Mathematics, Volume 33, Issue 3, Page 1121-1145, January 2019.
We consider the maximization problem of monotone submodular functions under an uncertain knapsack constraint. Specifically, the...

By Serge Gaspers and Shenwei Huang
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 1095-1120, January 2019.
In this paper, we show that every $(2P_2,K_4)$-free graph is 4-colorable. The bound is attained by...

By Matthias Walter
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 1061-1094, January 2019.
We consider, for complete bipartite graphs, the convex hulls of characteristic vectors of all matchings, extended...

By Abdul Basit and Ben Lund
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 1044-1060, January 2019.
We show that there exists an absolute constant $c > 0$, such that, for any finite...

By Jacob Focke, Leslie Ann Goldberg, and Stanislav Živný
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 1006-1043, January 2019.
A homomorphism from a graph $G$ to a graph $H$ is a function from the vertices...

By Mikhail Lavrov, Po-Shen Loh, and Arnau Messegué
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 994-1005, January 2019.
An $\epsilon$-distance-uniform graph is one with a critical distance $d$ such that from every vertex, all...

By Janko Gravner, J. E. Paguyo, and Erik Slivken
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 976-993, January 2019.
We consider a long-range growth dynamics on the two-dimensional integer lattice, initialized by a finite set...

By Paul Horn
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 958-975, January 2019.
The study of positive solutions of the heat equation $\frac{\partial}{\partial \alpha} u = \Delta u$, on...

By Edita Máčajová, Edita Rollová, and Martin Škoviera
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 933-957, January 2019.
We continue the study of circuit covers of signed graphs initiated by Máčajová et al. [J....

By Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman, and Kunal Talwar
SIAM Journal on Computing, Volume 48, Issue 3, Page 1120-1145, January 2019.
We prove that any graph excluding $K_r$ as a minor can be partitioned into clusters of diameter...

By Jean-Daniel Boissonnat, Mael Rouxel-Labbé, and Mathijs H. M. J. Wintraecken
SIAM Journal on Computing, Volume 48, Issue 3, Page 1046-1097, January 2019.
The construction of anisotropic triangulations is desirable for various applications, such as the numerical solving of partial...

By Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraëte
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 862-873, January 2019.
An $r$-uniform hypergraph is a tight $r$-tree if its edges can be ordered so that every...

By Hunter Spink
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 910-932, January 2019.
In 1979, Shearer and Kleitman conjectured the existence of $\lfloor n/2 \rfloor+1$ orthogonal chain decompositions of...

By Therese Biedl, Ahmad Biniaz, Robert Cummings, Anna Lubiw, Florin Manea, Dirk Nowotka, and Jeffrey Shallit
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 845-861, January 2019.
A rollercoaster is a sequence of real numbers for which every maximal contiguous subsequence---increasing or decreasing---has...

By T. Karthick and Frédéric Maffray
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 874-909, January 2019.
We elucidate the structure of $(P_6,C_4)$-free graphs by showing that every such graph either has a...

By Jess Banks, Robert Kleinberg, and Cristopher Moore
SIAM Journal on Computing, Volume 48, Issue 3, Page 1098-1119, January 2019.
We derive upper and lower bounds on the degree $d$ for which the Lovász $\vartheta$ function, or...

By Tomasz Schoen and Ilya D. Shkredov
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 837-844, January 2019.
We prove that if $A\subseteq [N]$ does not contain any solution to the equation $x_1+\dots+x_k=y_1+\dots+y_k$ with...

By Hubie Chen, Matt Valeriote, and Yuichi Yoshida
SIAM Journal on Computing, Volume 48, Issue 3, Page 1022-1045, January 2019.
For each finite relational structure $A$, let $CSP(A)$ denote the CSP instances whose constraint relations are taken...

By Heng Guo and Mark Jerrum
SIAM Journal on Computing, Volume 48, Issue 3, Page 964-978, January 2019.
We give a fully polynomial-time randomized approximation scheme (FPRAS) for the all-terminal network reliability problem, which is...

By Dieter van Melkebeek and Gautam Prakriya
SIAM Journal on Computing, Volume 48, Issue 3, Page 979-1021, January 2019.
We study the possibility of deterministic and randomness-efficient isolation in space-bounded models of computation: Can one efficiently...

By Fedor V. Fomin, Petr Golovach, Fahad Panolan, and Saket Saurabh
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 795-836, January 2019.
In the Edge Editing to Connected $f$-Degree Graph problem we are given a graph $G$, an...

By Boris Bukh and Xavier Goaoc
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 784-794, January 2019.
We study how a single value of the shatter function of a set system restricts its...

By Gábor Ivanyos and Youming Qiao
SIAM Journal on Computing, Volume 48, Issue 3, Page 926-963, January 2019.
We consider two basic algorithmic problems concerning tuples of (skew-)symmetric matrices. The first problem asks us to...

By Mahya Ghandehari and Jeannette Janssen
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 712-730, January 2019.
A square symmetric matrix is a Robinson similarity matrix if entries in its rows and columns...

By Hirotada Kobayashi, François Le Gall, and Harumichi Nishimura
SIAM Journal on Computing, Volume 48, Issue 3, Page 865-902, January 2019.
This paper investigates the role of interaction and coins in quantum Arthur--Merlin games (also called public-coin quantum...

By Yury Polyanskiy
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 731-754, January 2019.
Consider the linear space of functions on the binary hypercube and the linear operator $S_\delta$ acting...

By Amitabh Basu, Santanu S. Dey, and Joseph Paat
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 755-783, January 2019.
We explore the lifting question in the context of cut-generating functions. Most of the prior literature...

By Srinivasan Arunachalam, Jop Briët, and Carlos Palazuelos
SIAM Journal on Computing, Volume 48, Issue 3, Page 903-925, January 2019.
We prove a characterization of $t$-query quantum algorithms in terms of the unit ball of a space...

By Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, and Aaron Potechin
SIAM Journal on Computing, Volume 48, Issue 2, Page 687-735, January 2019.
We prove that with high probability over the choice of a random graph $G$ from the Erdös--Rényi...

By Nikhil Bansal, Daniel Dadush, and Shashwat Garg
SIAM Journal on Computing, Volume 48, Issue 2, Page 534-553, January 2019.
We consider the problem of finding a low discrepancy coloring for sparse set systems where each element...

By Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, Eric Vigoda, and Yitong Yin
SIAM Journal on Computing, Volume 48, Issue 2, Page 581-643, January 2019.
We study the hard-core (gas) model defined on independent sets of an input graph where the independent...

By Shiteng Chen and Periklis A. Papakonstantinou
SIAM Journal on Computing, Volume 48, Issue 2, Page 668-686, January 2019.
We show that every circuit with ${AND},{OR},{NOT}$, and ${MOD}_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth...

By W. T. Gowers and Emanuele Viola
SIAM Journal on Computing, Volume 48, Issue 2, Page 554-580, January 2019.
Let $G$ be the special linear group ${SL}(2,q)$. We show that if $(a_1,\ldots,a_t)$ and $(b_1,\ldots,b_t)$ are...

By Mathias Bæk Tejs Knudsen
SIAM Journal on Computing, Volume 48, Issue 2, Page 736-741, January 2019.
We consider the hash function $h(x) = ((ax+b)mod p)mod n$ where $a,b$ are chosen uniformly at random...

By Zachary Friggstad, Mohsen Rezapour, and Mohammad R. Salavatipour
SIAM Journal on Computing, Volume 48, Issue 2, Page 452-480, January 2019.
The most well-known and ubiquitous clustering problem encountered in nearly every branch of science is undoubtedly $k$-means:...

By Vincent Cohen-Addad, Philip N. Klein, and Claire Mathieu
SIAM Journal on Computing, Volume 48, Issue 2, Page 644-667, January 2019.
We give the first polynomial-time approximation schemes (PTASs) for the following problems: (1) uniform facility location in...

By Zihan Tan and Liwei Zeng
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 694-711, January 2019.
We study the following geometry problem: given a $2^n-1$ dimensional vector $\pi=\{\pi_S\}_{S\subseteq [n], S\ne \emptyset}$, is...

By Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart
SIAM Journal on Computing, Volume 48, Issue 2, Page 742-864, January 2019.
We study high-dimensional distribution learning in an agnostic setting where an adversary is allowed to arbitrarily corrupt...

By Yijia Chen and Bingkai Lin
SIAM Journal on Computing, Volume 48, Issue 2, Page 513-533, January 2019.
A set $D$ of vertices of a graph $G$ is a dominating set if every vertex of...

By Karl Bringmann, Fabrizio Grandoni, Barna Saha, and Virginia Vassilevska Williams
SIAM Journal on Computing, Volume 48, Issue 2, Page 481-512, January 2019.
It is a major open problem whether the $(\min,+)$-product of two $n\times n$ matrices has a truly...

By Irit Dinur, Or Meir, and Swastik Kopparty
SIAM Journal on Computing, Volume 48, Issue 2, Page 451-451, January 2019.
This special section comprises eleven fully refereed papers whose extended abstracts were presented at the 57th Annual...

By Nir Weinberger and Ofer Shayevitz
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 665-693, January 2019.
A Boolean function $g$ is said to be an optimal predictor for another Boolean function $f$...

By Marek Cygan, Daniel Lokshtanov, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh
SIAM Journal on Computing, Volume 48, Issue 2, Page 417-450, January 2019.
In the classic Minimum Bisection problem we are given as input an undirected graph $G$ and an...

By Václav Rozhoň
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 643-664, January 2019.
A famous conjecture of Erd\Hos and Sós states that every graph with average degree more than...

By Jing Chen, Bo Li, and Yingkai Li
SIAM Journal on Computing, Volume 48, Issue 2, Page 373-416, January 2019.
The dispersion problem has been widely studied in computational geometry and facility location and is closely related...

By Noga Alon and Nadav Sherman
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 629-642, January 2019.
We prove that the minimum number of vertices of a hypergraph that contains every $d$-uniform hypergraph...

By Daniel W. Cranston
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 614-628, January 2019.
An acyclic edge-coloring of a graph $G$ is a proper edge-coloring of $G$ such that the...

By Alessio Conte, Roberto Grossi, Andrea Marino, and Luca Versari
SIAM Journal on Discrete Mathematics, Volume 33, Issue 2, Page 587-613, January 2019.
Algorithms for listing the subgraphs satisfying a given property (e.g., being a clique, a cut, a...

By Flavio Chierichetti, Ravi Kumar, Alessandro Panconesi, and Erisa Terolli
SIAM Journal on Computing, Volume 48, Issue 2, Page 350-372, January 2019.
Given a notion of pairwise similarity between objects, locality sensitive hashing (LSH) aims to construct a hash...

By Ivona Bezáková, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Daniel Štefankovič
SIAM Journal on Computing, Volume 48, Issue 2, Page 279-349, January 2019.
Approximate counting via correlation decay is the core algorithmic technique used in the sharp delineation of the...

By Jaehoon Kim, Younjin Kim, and Hong Liu
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 564-586, January 2019.
Given graphs $H_1,\ldots, H_k$, a graph $G$ is $(H_1,\ldots, H_k)$-free if there is a $k$-edge-coloring $\phi:E(G)\rightarrow...

By Arnold Filtser
SIAM Journal on Computing, Volume 48, Issue 2, Page 249-278, January 2019.
In the Steiner point removal problem, we are given a weighted graph $G=(V,E)$ and a set of...

By Ittai Abraham and Ofer Neiman
SIAM Journal on Computing, Volume 48, Issue 2, Page 227-248, January 2019.
We prove that any weighted graph $G=(V,E,w)$ with $n$ points and $m$ edges has a spanning tree...

By Roee David, Karthik C. S., and Bundit Laekhanukit
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 509-527, January 2019.
Every graph $G$ can be represented by a collection of equi-radii spheres in a $d$-dimensional metric...

By Michael Anastos and Alan Frieze
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 528-545, January 2019.
We consider the existence of patterned Hamilton cycles in randomly colored random graphs. Given a string...

By David G. Harris
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 546-563, January 2019.
A variety of powerful extremal results have been shown for the chromatic number of triangle-free graphs....

By Béla Csaba and Judit Nagy-György
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 474-508, January 2019.
Let $H$ and $G$ be graphs on $n$ vertices, where $n$ is sufficiently large. We prove...

By Anastasios Sidiropoulos, Mihai Badoiu, Kedar Dhamdhere, Anupam Gupta, Piotr Indyk, Yuri Rabinovich, Harald Racke, and R. Ravi
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 454-473, January 2019.
We present several approximation algorithms for the problem of embedding metric spaces into a line, and...

By Nathan Keller and Noam Lifshitz
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 398-401, January 2019.
A family ${\cal F}$ of graphs on a fixed set of $n$ vertices is called triangle-intersecting...

By Giacomo Micheli and Violetta Weger
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 425-437, January 2019.
Let $n$ and $m$ be positive integers such that $n

By Carlos Hoppen, Roberto F. Parente, and Cristiane M. Sato
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 438-453, January 2019.
We study the problem of packing arborescences in the random digraph $\mathcal D(n,p)$, where each possible...

By Ishay Haviv
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 402-424, January 2019.
A set of integers is sum-free if it contains no solution to the equation $x+y=z$. We...

By Guantao Chen, Xing Feng, Fuliang Lu, and Lianzhu Zhang
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 393-397, January 2019.
Carvalho, Lucchesi, and Murty [J. Combin. Theory Ser. B, 92 (2004), pp. 319--324, Theorem 3.5] presented...

By András Gyárfás
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 383-392, January 2019.
A Berge-K_4 in a triple system is a configuration with four vertices $v_1,v_2,v_3,v_4$ and six distinct...

By Rotem Arnon-Friedman, Renato Renner, and Thomas Vidick
SIAM Journal on Computing, Volume 48, Issue 1, Page 181-225, January 2019.
Device-independent security is the gold standard for quantum cryptography: not only is security based entirely on the...

By Mrinal Kumar and Ramprasad Saptharishi
SIAM Journal on Computing, Volume 48, Issue 1, Page 144-180, January 2019.
Surprising and beautiful depth reduction results show that sufficiently strong lower bounds for bounded-depth arithmetic circuits imply...

By Nick Brettell, Rutger Campbell, Deborah Chun, Kevin Grace, and Geoff Whittle
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 358-372, January 2019.
We consider matroids with the property that every subset of the ground set of size $t$...

By Peter Nelson and Jorn van der Pol
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 373-382, January 2019.
A biased graph is a graph $G$, together with a distinguished subset $\mathcal{B}$ of its cycles,...

By Daniel Weißauer
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 346-357, January 2019.
A $k$-block in a graph $G$ is a maximal set of at least $k$ vertices no...

By Shiping Liu, Florentin Münch, and Norbert Peyerimhoff
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 257-305, January 2019.
We study the eigenvalues of the connection Laplacian on a graph with an orthogonal group or...

By Carolina Medina, Jorge Ramírez-Alfonsín, and Gelasio Salazar
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 306-326, January 2019.
Let $D$ be a knot diagram, and let ${\mathcal D}$ denote the set of diagrams that...

By Fedor V. Fomin, Petteri Kaski, Daniel Lokshtanov, Fahad Panolan, and Saket Saurabh
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 327-345, January 2019.
In the Steiner Tree problem, we are given as input a connected $n$-vertex graph with edge...

By Yi-Jun Chang, Tsvi Kopelowitz, and Seth Pettie
SIAM Journal on Computing, Volume 48, Issue 1, Page 122-143, January 2019.
Over the past 30 years numerous algorithms have been designed for symmetry breaking problems in the LOCAL...

By Deng Tang, Selçuk Kavut, Bimal Mandal, and Subhamoy Maitra
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 238-256, January 2019.
Very recently, a class of cryptographically significant Boolean functions were constructed by Tang and Maitra [IEEE...

By Hao Huang and Jie Ma
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 230-237, January 2019.
A tight $k$-uniform $\ell$-cycle, denoted by $TC_\ell^k$, is a $k$-uniform hypergraph whose vertex set is $v_0,...

By Yeow Meng Chee, Fei Gao, Han Mao Kiah, Alan Chi Hung Ling, Hui Zhang, and Xiande Zhang
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 209-229, January 2019.
We demonstrate that certain Johnson-type bounds are asymptotically exact for a variety of classes of codes,...

By G. O. Mota
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 197-208, January 2019.
We estimate the 3-color bipartite Ramsey number for balanced bipartite graphs $H$ with small bandwidth and...

By Neil J. Y. Fan, Peter L. Guo, and Sophie C. C. Sun
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 189-196, January 2019.
Barely set-valued tableaux were introduced by Reiner, Tenner, and Yong in their study of the probability...

By James Oxley
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 138-152, January 2019.
Adding elements to matroids can be fraught with difficulty. In the Vámos matroid $V_8$, there are...

By Stephen Alstrup, Haim Kaplan, Mikkel Thorup, and Uri Zwick
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 116-137, January 2019.
We describe a way of assigning labels to the vertices of any undirected graph on up...

By Robert Hancock, Katherine Staden, and Andrew Treglown
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 153-188, January 2019.
Many important problems in combinatorics and other related areas can be phrased in the language of...

By Thomas Kalinowski, Nina Kamčev, and Benny Sudakov
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 95-115, January 2019.
A subset $S$ of initially infected vertices of a graph $G$ is called zero forcing if...

By Sungjin Im, Nathaniel Kell, Janardhan Kulkarni, and Debmalya Panigrahi
SIAM Journal on Computing, Volume 48, Issue 1, Page 93-121, January 2019.
Modern data centers face a key challenge of effectively serving user requests that arrive online. Such requests...

By Suryajith Chillara, Nutan Limaye, and Srikanth Srinivasan
SIAM Journal on Computing, Volume 48, Issue 1, Page 70-92, January 2019.
The complexity of Iterated Matrix Multiplication (IMM) is a central theme in Computational Complexity theory, as the...

By Robert Hancock
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 68-94, January 2019.
Given an integer-valued matrix $A$ of dimension $\ell \times k$ and an integer-valued vector $b$ of...

By Kevin Grace and Stefan H. M. van Zwam
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 26-67, January 2019.
The classes of even-cycle matroids, even-cycle matroids with a blocking pair, and even-cut matroids each have...

By Yi-Jun Chang and Seth Pettie
SIAM Journal on Computing, Volume 48, Issue 1, Page 33-69, January 2019.
The celebrated time hierarchy theorem for Turing machines states, informally, that more problems can be solved given...

By Hagit Attiya, Armando Castan͂eda, Maurice Herlihy, and Ami Paz
SIAM Journal on Computing, Volume 48, Issue 1, Page 1-32, January 2019.
The $M(n)$-renaming task requires $n+1$ processes, each starting with a unique input name (from an arbitrary large...

By Sean Kafer, Kanstantsin Pashkovich, and Laura Sanità
SIAM Journal on Discrete Mathematics, Volume 33, Issue 1, Page 1-25, January 2019.
The combinatorial diameter of a polytope $P$ is the maximum value of a shortest path between...

This prize was created in 2013 to emphasize George Pólya’s legacy of communicating mathematics effectively. It joins two long-standing Pólya prizes SIAM has awarded in combinatorics and other fields beginning in 1969.

This prize is intended to emphasize applications of combinatorics and is funded by the estate of Stella Pólya in memory of her husband George. The prize will first be awarded in 2020, and is a modification of the older George Pólya Prize in Combinatorics, originally established as the George Pólya Prize in 1969.

Through the generosity and inspiration of Gerald and Judith Porter, the Mathematical Association of America (MAA), American Mathematical Society (AMS), and SIAM offer this annual lecture at the Joint Mathematics Meetings. The lecture, first awarded in 2010, is given on a mathematical topic accessible to the broader community.

Named in honor of I. E. Block, a co-founder and the first managing director of SIAM, this lecture is open to the public at the SIAM Annual Meeting. It is intended to encourage public appreciation of applied mathematics and computational science by reaching out to the local community.

Established in 1959, the prize honors John von Neumann, a founder of modern computing. The prize is awarded annually for distinguished contributions to applied mathematics and for the effective communication of these ideas to the community.

The JPBM Communications Award is given annually to reward and encourage communicators who, on a sustained basis, bring mathematical ideas and information to non-mathematical audiences. The prize may be awarded in two categories: For Public Outreach and For Expository and Popular Books. Nominations can be submitted via the AMS website.

Open for Nominations

~*Learn More*~

Established in 1998 in memory of Ralph E. Kleinman, the prize recognizes contributions that bridge the gap between high-level mathematics and engineering problems. The award is based on the quality and impact of the mathematics.

The prize was established in 1986 in memory of Richard C. DiPrima, who served SIAM for many years and in 1979–1980 as SIAM President. It aims to recognize an early career researcher in applied mathematics and is based on the doctoral dissertation.

The prize recognizes students for outstanding solutions to real world math problems. It is awarded to two of the teams judged "Outstanding" in the Mathematical Contest in Modeling (MCM) administered annually by the Consortium for Mathematics and Its Applications (COMAP). Registration is accepted via the COMAP website.

The SIAM Outstanding Paper Prizes bring attention to papers published in SIAM journals. Three awards are made each year to the authors of papers deemed by SIAM journal editors-in-chief worthy of particular attention.

The prize, established in 1985 and originally intended to be awarded periodically, is now awarded annually for contributions to the advancement of applied mathematics on the national or international level.