Researchers in this area have established important connections with mainstream areas of pure and applied mathematics, and research techniques are drawn from a range of fields, including algebra, topology, geometry, probability, analysis, and logic.

By Luca Becchetti, Andrea E. Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan SIAM Journal on Computing, Volume 49, Issue 4, Page 821-864, January 2020. Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in...

By Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1710-1724, January 2020. We unify several seemingly different graph and digraph classes under one umbrella. These classes are...

By Matthew Coulson and Guillem Perarnau SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1670-1692, January 2020. A famous theorem of Dirac states that any graph on $n$ vertices with minimum degree at...

By Sungjin Im, Shi Li, and Benjamin Moseley SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1649-1669, January 2020. In this paper we consider one of the most basic scheduling problems where jobs have their...

By Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1693-1709, January 2020. We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if...

By William M. Hoza and David Zuckerman SIAM Journal on Computing, Volume 49, Issue 4, Page 811-820, January 2020. We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length...

By Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1623-1648, January 2020. For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph...

By Luca Becchetti, Andrea E. Clementi, Emanuele Natale, Francesco Pasquale, and Luca Trevisan SIAM Journal on Computing, Volume 49, Issue 4, Page 821-864, January 2020. Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in...

By Pavol Hell, Jing Huang, Ross M. McConnell, and Arash Rafiey SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1710-1724, January 2020. We unify several seemingly different graph and digraph classes under one umbrella. These classes are...

By Matthew Coulson and Guillem Perarnau SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1670-1692, January 2020. A famous theorem of Dirac states that any graph on $n$ vertices with minimum degree at...

By Sungjin Im, Shi Li, and Benjamin Moseley SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1649-1669, January 2020. In this paper we consider one of the most basic scheduling problems where jobs have their...

By Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. Wood SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1693-1709, January 2020. We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if...

By William M. Hoza and David Zuckerman SIAM Journal on Computing, Volume 49, Issue 4, Page 811-820, January 2020. We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length...

By Julien Baste, Ignasi Sau, and Dimitrios M. Thilikos SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1623-1648, January 2020. For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph...

By Wouter Cames van Batenburg, Gwenaël Joret, and Arthur Ulmer SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1609-1619, January 2020. A classic theorem of Erdös and Pósa [Canad. J. Math., 17 (1965), pp. 347--352] states that...

By Boris Bukh and Oleksandr Rudenko SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1620-1622, January 2020. Let $a_1,\ldots,a_n$ be a permutation of $[n]$. Two disjoint order-isomorphic subsequences are called twins. We show...

By Hailong Dao, Joseph Doolittle, and Justin Lyle SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1602-1608, January 2020. We define and study the notion of a minimal Cohen--Macaulay simplicial complex. We prove that any...

By Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca Trevisan SIAM Journal on Computing, Volume 49, Issue 4, Page 772-810, January 2020. We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms,...

By Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav Zehavi SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1587-1601, January 2020. An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree...

By Abigail Raz SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1559-1586, January 2020. This paper examines bounds on upper tails for cycle counts in $G_{n,p}$. For a fixed graph...

By Talya Eden, Dana Ron, and C. Seshadhri SIAM Journal on Computing, Volume 49, Issue 4, Page 747-771, January 2020. We study the problem of approximating the number of $k$-cliques in a graph when given query access...

By Michael Lampis SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1538-1558, January 2020. We revisit the complexity of the classical $k$-Coloring problem parameterized by clique-width. This is a very...

By David G. Harris SIAM Journal on Computing, Volume 49, Issue 4, Page 711-746, January 2020. We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in...

By Tara Fife, Dillon Mayhew, James Oxley, and Charles Semple SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1522-1537, January 2020. A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$...

By Chong Shangguan and Itzhak Tamo SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1493-1504, January 2020. For fixed integers $r\ge 3,e\ge 3,v\ge r+1$, an $r$-uniform hypergraph is called $\mathscr{G}_r(v,e)$-free if the union...

By Pasin Manurangsi and Warut Suksompong SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1505-1521, January 2020. We consider a fair division setting in which $m$ indivisible items are to be allocated among...

By Matthew Jenssen, Peter Keevash, and Will Perkins SIAM Journal on Computing, Volume 49, Issue 4, Page 681-710, January 2020. We give a fully polynomial-time approximation scheme (FPTAS) and an efficient sampling algorithm for the high-fugacity hard-core...

By Hui Zhu, Liying Kang, Zhenyu Ni, and Erfang Shan SIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1485-1492, January 2020. For a graph $G=(V,E)$, a hypergraph $H$ is called a Berge-$G$ if there is a bijection...

By Scott Aaronson SIAM Journal on Computing, Ahead of Print. We introduce the problem of shadow tomography: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$,...

By Ivailo Hartarsky and Tamás Róbert Mezei SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1444-1459, January 2020. Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models...

By Sungjin Im and Benjamin Moseley SIAM Journal on Computing, Volume 49, Issue 3, Page 658-680, January 2020. This paper considers minimizing the $\ell_k$-norms of flow time on a single machine offline using a preemptive...

By Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1472-1483, January 2020. A hole in a graph is an induced cycle of length at least 4, and an...

By Sebastián Bustamante, Jan Corsten, Nóra Frankl, Alexey Pokrovskiy, and Jozef Skokan SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1460-1471, January 2020. Confirming a conjecture of Gyárfás, we prove that, for all natural numbers $k$ and $r$, the...

By Karthekeyan Chandrasekaran, Matthias Mnich, and Sahand Mozaffari SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1385-1408, January 2020. We investigate the odd multiway node (edge) cut problem where the input is a graph with...

By Alexander Birx and Yann Disser SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1409-1443, January 2020. The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests...

By Seyyed Aliasghar Hosseini, Fiachra Knox, and Bojan Mohar SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1375-1384, January 2020. The game of Cops and Robbers is a well-known game played on graphs. In this paper,...

By Debsoumya Chakraborti and Po-Shen Loh SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1354-1374, January 2020. We systematically study a natural problem in extremal graph theory, to minimize the number of edges...

By Chandra Chekuri, Kent Quanrud, and Chao Xu SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1334-1353, January 2020. Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46--76] to derive...

By Dan Feldman, Melanie Schmidt, and Christian Sohler SIAM Journal on Computing, Volume 49, Issue 3, Page 601-657, January 2020. We develop and analyze a method to reduce the size of a very large set of data...

By Danila Cherkashin and Fedor Petrov SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1326-1333, January 2020. Let $m(n,r)$ denote the minimal number of edges in an $n$-uniform hypergraph which is not $r$-colorable....

By Jun Gao and Jie Ma SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1290-1301, January 2020. Answering a question of Häggkvist and Scott, Verstraëte proved that every sufficiently large graph with average...

By Neil J. Y. Fan, Peter L. Guo, Simon C. Y. Peng, and Sophie C. C. Sun SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1281-1289, January 2020. We confirm a conjecture of Monical, Tokcan, and Yong on a characterization of the lattice points...

By Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar Tale SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1302-1325, January 2020. A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq...

By Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang SIAM Journal on Computing, Ahead of Print. We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition, which is a decomposition of...

By Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones SIAM Journal on Computing, Volume 49, Issue 3, Page 583-600, January 2020. For any constant $d$ and parameter $\varepsilon \in (0,1/2]$, we show the existence of (roughly) $1/\varepsilon^d$ orderings...

By Christian Haase, Florian Kohl, and Akiyoshi Tsuchiya SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1261-1280, January 2020. Since Stanley's [Discrete Comput. Geom., 1 (1986), pp. 9--23] introduction of order polytopes, their geometry has...

By Pavel Etingof SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1248-1260, January 2020. The goal of this paper is to give a systematic method of constructing zero-free regions for...

By Paul Beame, Shayan Oveis Gharan, and Xin Yang SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1232-1247, January 2020. We study the bias of random bounded-degree polynomials over odd prime fields and show that, with...

By Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan Lucier SIAM Journal on Computing, Volume 49, Issue 3, Page 540-582, January 2020. We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes...

By Sean Dewar SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1205-1231, January 2020. We prove that a graph has an infinitesimally rigid placement in a non-Euclidean normed plane if...

By Yezhou Wu and Dong Ye SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1192-1204, January 2020. Let $G$ be a graph with edge set $E(G)$ and vertex set $V(G)$, and let $T$...

By Michael Joswig and Georg Loho SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1172-1191, January 2020. We present an algorithm to compute all $n$ nondominated points of a multicriteria discrete optimization problem...

By Yi-Jun Chang, Wenzheng Li, and Seth Pettie SIAM Journal on Computing, Volume 49, Issue 3, Page 497-539, January 2020. Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper,...

By R. Gabrys, H. S. Dau, C. J. Colbourn, and O. Milenkovic SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1148-1171, January 2020. We address the new problem of designing large families of subsets of a common labeled ground...

By Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, and Avi Wigderson SIAM Journal on Computing, Volume 49, Issue 3, Page 465-496, January 2020. We introduce a simple logical inference structure we call a “spanoid" (generalizing the notion of a...

By Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor Zamaraev SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1107-1147, January 2020. Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class...

By Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole Wein SIAM Journal on Computing, Volume 49, Issue 2, Page 448-464, January 2020. We propose a new distribution-free model of social networks. Our definitions are motivated by one of the...

By Rémy Belmonte, Michael Lampis, and Valia Mitsou SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1084-1106, January 2020. In Defective Coloring we are given a graph $G=(V,E)$ and two integers ${\chi_d},\Delta^*$ and are asked...

By Bhaswar B. Bhattacharya and Shirshendu Ganguly SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1069-1083, January 2020. The upper tail problem for the largest eigenvalue of the Erdös--Rényi random graph $\mathcal{G}_{n,p}$ is to...

By Shi Li SIAM Journal on Computing, Ahead of Print. We study approximation algorithms for problems of scheduling precedence constrained jobs with the objective of minimizing total weighted completion time, in identical...

By Arnold Filtser and Shay Solomon SIAM Journal on Computing, Volume 49, Issue 2, Page 429-447, January 2020. The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it...

By Benjamin Plaut and Tim Roughgarden SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1039-1068, January 2020. The goal of fair division is to distribute resources among competing players in a “fair" way....

By Toufik Mansour, Reza Rastegar, and Alexander Roitershtein SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1011-1038, January 2020. The main theme of this paper is the enumeration of the order-isomorphic occurrence of a pattern...

By Nicholas J. A. Harvey and Jan Vondrák SIAM Journal on Computing, Volume 49, Issue 2, Page 394-428, January 2020. The Lovász local lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on...

By Rajko Nenadov and Yanitsa Pehova SIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1001-1010, January 2020. A seminal result of Hajnal and Szemerédi states that if a graph $G$ with $n$ vertices...

By Zihan Tan and Liwei Zeng SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 1000-1000, January 2020. This note is an erratum for the paper On the Inequalities of Projected Volumes and the...

By Uriel Feige, Anne Kenyon, and Shimon Kogan SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 950-971, January 2020. Let $G$ be a 2-coloring of a complete graph on $n$ vertices, for sufficiently large $n$....

By O-joung Kwon and Sang-il Oum SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 972-999, January 2020. For a class $\mathcal C$ of graphs $G$ equipped with functions $f_G$ defined on subsets...

By Ken Yamamoto SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 938-949, January 2020. The Horton--Strahler analysis is a graph-theoretic method to measure the bifurcation complexity of branching patterns, by...

By Libor Barto and Michael Pinsker SIAM Journal on Computing, Volume 49, Issue 2, Page 365-393, January 2020. The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated that such CSPs are solvable...

By Rajesh H. Chitnis, Andreas E. Feldmann, MohammadTaghi HajiAghayi, and Daniel Marx SIAM Journal on Computing, Volume 49, Issue 2, Page 318-364, January 2020. Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2, \ldots, t_k\}$ of $k$ terminals, the...

By Alantha Newman SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 865-884, January 2020. Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph...

By Ran Gelles, Rafail Ostrovsky, and Alan Roytman SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 904-937, January 2020. We consider the task of communicating an (infinite) data stream in the sliding window model, where...

By Noga Alon, Jonathan D. Cohen, Thomas L Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, and Alexander Yu SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 885-903, January 2020. We consider the problem of determining the maximal $\alpha \in (0,1]$ such that every matching $M$...

By Khaled Elbassioni and Kazuhisa Makino SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 843-864, January 2020. We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $P=P(A,\b1)=\{x\in \mathbb{R}^n...

By Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling, and Hengjia Wei SIAM Journal on Computing, Volume 49, Issue 2, Page 284-317, January 2020. A robust positioning pattern is a large array that allows a mobile device to locate its position...

By Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič, Eric Vigoda, and Kuan Yang SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 742-793, January 2020. We consider the problem of sampling from the Potts model on random regular graphs. It is...

By Silvia Butti and Stanislav Živný SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 825-842, January 2020. A cut $\varepsilon$-sparsifier of a weighted graph $G$ is a reweighted subgraph of $G$ of (quasi)linear...

By Bhaswar B. Bhattacharya, Somabha Mukherjee, and Sumit Mukherjee SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 794-824, January 2020. What is the chance that among a group of $n$ friends, there are $s$ friends all...

By Christian Engels, Mohit Garg, Kazuhisa Makino, and Anup Rao SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 730-741, January 2020. If $k

By Kasper Green Larsen, Omri Weinstein, and Huacheng Yu SIAM Journal on Computing, Ahead of Print. This paper proves the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean (also known as decision) data structure...

By Boris Bukh and Raymond Hogenson SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 721-729, January 2020. Given two random finite sequences from $[k]^n$ such that a prefix of the first sequence is...

By Daniel Irving Bernstein SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 701-720, January 2020. Given a dissimilarity map $\delta$ on a finite set $X$, the set of ultrametrics (equidistant tree...

By F. Becker, P. Montealegre, I. Rapaport, and I. Todinca SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 682-700, January 2020. The broadcast congested clique model (BClique) is a message-passing model of distributed computation where $n$ nodes...

By David Durfee, John Peebles, Richard Peng, and Anup B. Rao SIAM Journal on Computing, Ahead of Print. We show that variants of spectral sparsification routines can preserve the total spanning tree counts of graphs. By Kirchhoff's matrix-tree theorem, this...

By Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 640-681, January 2020. A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can...

By Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous SIAM Journal on Computing, Volume 49, Issue 2, Page 245-283, January 2020. Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable...

By Cody D. Murray and R. Ryan Williams SIAM Journal on Computing, Ahead of Print. We prove that if every problem in ${NP}$ has $n^k$-size circuits for a fixed constant $k$, then for every ${NP}$-verifier and every...

By Xin Fang, Ghislain Fourier, Jan-Philipp Litza, and Christoph Pegel SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 611-639, January 2020. For any marked poset we define a continuous family of polytopes, parametrized by a hypercube, generalizing...

By Kevin G. Milans and Michael C. Wigal SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 586-596, January 2020. First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let...

By Junpei Nakashima, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 571-585, January 2020. A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq...

By Peter J. Dukes and Daniel Horsley SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 597-610, January 2020. We prove that, for sufficiently large $n$, every graph of order $n$ with minimum degree at...

By Tao Jiang and Yu Qiu SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 556-570, January 2020. Given a graph $H$, the Turán number $\mathrm{ex}(n,H)$ is the largest number of edges in an...

By Vera Traub and Jens Vygen SIAM Journal on Computing, Ahead of Print. Among various variants of the traveling salesman problem (TSP), the $s$-$t$-path graph TSP has the special feature that we know the...

By Benjamin Plaut and Tim Roughgarden SIAM Journal on Computing, Volume 49, Issue 1, Page 206-243, January 2020. We initiate the study of the communication complexity of fair division with indivisible goods. We focus on...

By Zdeněk Dvořák and Xiaolan Hu SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 538-555, January 2020. A graph $G$ is $(a:b)$-colorable if there exists an assignment of $b$-element subsets of $\{1,\ldots,a\}$ to...

By Venkatesan Guruswami and Sai Sandeep SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 520-537, January 2020. A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its...

By Martin Grohe, Daniel Neuen, and Pascal Schweitzer SIAM Journal on Computing, Ahead of Print. In a recent breakthrough, Babai [Proceedings of STOC, ACM, New York, 2016, pp. 684--697] gave a quasipolynomial-time graph isomorphism test. In this...

By Marcel K. de Carli Silva and Levent Tunçel SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 470-496, January 2020. Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that...

By Daniel W. Cranston and Jiaao Li SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 497-519, January 2020. For integers $a\ge 2b>0$, a circular $a/b$-flow is a flow that takes values from $\{\pm b,...

By Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian Zhong SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 431-469, January 2020. A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We characterize all...

By Stasys Jukna and Hannes Seiwert SIAM Journal on Computing, Volume 49, Issue 1, Page 170-205, January 2020. We prove the first, even superpolynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits...

By Rasmus Kyng and Peng Zhang SIAM Journal on Computing, Ahead of Print. We show that if the nearly linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly...

By Mark Braverman, Gil Cohen, and Sumegha Garg SIAM Journal on Computing, Ahead of Print. Nisan [Combinatorica, 12 (1992), pp. 449--461] constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$...

By Emanuele Viola SIAM Journal on Computing, Volume 49, Issue 1, Page 119-137, January 2020. We show that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of $2^{m-m^{\Omega(1)}}$ restrictions...

By Jesús A. De Loera, Jamie Haddock, and Luis Rademacher SIAM Journal on Computing, Volume 49, Issue 1, Page 138-169, January 2020. The complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has...

By David Conlon, Jacob Fox, and Benny Sudakov SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 385-398, January 2020. A celebrated result of Mantel shows that every graph on n vertices with $\lfloor n^2/4 \rfloor...

By Laure Marêché SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 370-384, January 2020. We study the set of possible configurations for a general kinetically constrained model (KCM), a nonmonotone...

By Joshua Erde SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 415-430, January 2020. Many of the tools developed for the theory of tree-decompositions of graphs do not work for...

By Dániel Gerbner, Abhishek Methuku, Gholamreza Omidi, and Máté Vizer SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 351-369, January 2020. For a graph G, a hypergraph $\mathcal{H}$ is a Berge copy of G (or a Berge-G...

By Brant Jones SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 399-414, January 2020. The game of best choice (also known as the secretary problem) is a model for sequential...

By Christoph Berkholz and Jakob Nordström SIAM Journal on Computing, Volume 49, Issue 1, Page 98-118, January 2020. We show that there are CNF formulas which can be refuted in resolution in both small space...

By Ran Gu, Jiaao Li, and Yongtang Shi SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 271-307, January 2020. The anti-Ramsey problem was introduced by Erdös, Simonovits, and Sós in 1970s. The anti-Ramsey number of...

By Marcin Wrochna SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 328-350, January 2020. For a fixed graph H, we consider the H-Recoloring problem: given a graph G and two...

By Alexander Barvinok and Anthony Della Pella SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 308-327, January 2020. For a set S of vertices of a graph G, we define its density 0 łeq...

By Uriel Feige, Michal Feldman, and Inbal Talgam-Cohen SIAM Journal on Computing, Volume 49, Issue 1, Page 67-97, January 2020. Set functions with convenient properties (such as submodularity) appear in application areas of current interest, such as...

By Samir Khuller, Manish Purohit, and Kanthi K. Sarpatwar SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 251-270, January 2020. We study partial and budgeted versions of the well-studied connected dominating set problem. In the...

By Huijia Lin, Rafael Pass, and Pratik Soni SIAM Journal on Computing, Ahead of Print. Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991,...

By Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan SIAM Journal on Computing, Ahead of Print. It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct...

By Dániel Garamvölgyi and Tibor Jordán SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 212-229, January 2020. A $d$-dimensional bar-and-joint framework $(G,p)$, where $G$ is a graph and $p$ maps the vertices of...

By Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, and Clifford Stein SIAM Journal on Computing, Volume 49, Issue 1, Page 37-66, January 2020. We consider virtual circuit routing protocols with an objective of minimizing energy in a network of components...

By Anurag Bishnoi and Valentina Pepe SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 230-240, January 2020. A famous conjecture of Ryser states that every $r$-partite hypergraph has vertex cover number ...

By Robert Lukoťka SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 188-211, January 2020. A cycle cover of a graph is a collection of cycles such that each edge of...

By Oliver Janzer SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 241-250, January 2020. For a graph $F$, the $k$-subdivision of $F$, denoted $F^k$, is the graph obtained by replacing...

By Gramoz Goranci, Monika Henzinger, and Pan Peng SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 130-162, January 2020. Graph sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the...

By Sara Fish, Cosmin Pohoata, and Adam Sheffer SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 177-187, January 2020. The local properties problem of Erd\Hos and Shelah generalizes many Ramsey problems and some distinct distances...

By Tony Huynh and Peter Nelson SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 163-176, January 2020. We prove that for every proper minor-closed class $\mathcal{M}$ of $\mathbb{F}_p$-representable matroids, there exists an $O(1)$-competitive...

By František Kardoš SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 62-100, January 2020. Fullerene graphs, i.e., 3-connected planar cubic graphs with pentagonal and hexagonal faces, are conjectured to be...

By Monika Henzinger, Satish Rao, and Di Wang SIAM Journal on Computing, Volume 49, Issue 1, Page 1-36, January 2020. We study the problem of computing a minimum cut in a simple, undirected graph and give a...

By Robert Krauthgamer and Havana Inbal Rika SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 101-129, January 2020. We study the following version of cut sparsification. Given a large edge-weighted network $G$ with $k$...

By Michaĺ Deͅbski, Jarosław Grytczuk, Barbara Nayar, Urszula Pastwa, Joanna Sokół, Michał Tuczyński, Przemysław Wenus, and Krzysztof Weͅsek SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 40-52, January 2020. We study colorings of Euclidean spaces avoiding specified patterns on straight lines. This extends the seminal...

By Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon Sering SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 1-39, January 2020. The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon and an...

By Alan M. Frieze and Tomasz Tkocz SIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 53-61, January 2020. We study the component structure of the random graph $G=G_{n,m,d}$. Here $d=O(1)$ and $G$ is sampled...

By Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma SIAM Journal on Computing, Ahead of Print. The breakthrough result of Chattopadhyay and Zuckerman [Explicit two-source extractors and resilient functions, in Proceedings of the 48th Annual ACM SIGACT Symposium...

By Rishab Goyal, Venkata Koppula, and Brent Waters SIAM Journal on Computing, Ahead of Print. In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in $\log(n)$, where $n$ is the number of...

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 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 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 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 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...

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 is a modification of the older George Pólya Prize in Combinatorics, originally established as the George Pólya Prize in 1969.

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.

This joint prize was established in 2002 to honor Sonia Kovalevsky and her work on the theory of differential equations. It is awarded to anyone in the scientific or engineering community whose work highlights the achievements of women in applied and computational mathematics. Nominations can be submitted via the AWM website.

The Pioneer Prize is awarded every four years at the International Council for Industrial and Applied Mathematics (ICIAM) Congress to one individual for pioneering work introducing applied mathematical methods and scientific computing techniques to an industrial problem area or a new scientific field of applications. Nominations can be submitted via the ICIAM website.

Established in 1967, the prize honors Norbert Wiener, a founder of the field of cybernetics. The prize is awarded every three years by SIAM and the American Mathematical Society (AMS) for an outstanding contribution to applied mathematics. Nominations can be submitted via the AMS website.

Established in 2007, the prize honors Dénes König, a pioneer of discrete mathematics still influencing the field. It is awarded for outstanding research by an individual in their early career, based on publication in peer-reviewed journals.

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.

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.

The SIAM Student Paper Prize is awarded annually to the student author(s) of the most outstanding paper(s) accepted by SIAM journals within the three years preceding the nomination deadline. Starting with the 2018 award, the focus of the prize is to recognize outstanding scholarship by students in SIAM journals.

This activity group focuses on unifying pure discrete mathematics and areas of applied research such as computer science, operations research, combinatorics, and the social sciences. Other areas the group focuses on include combinatorics, graph theory, cryptography, discrete optimization, mathematical programming, coding theory, information theory, game theory, and theoretical computer science, including algorithms, complexity, circuit design, robotics, and parallel processing.

SIAM Journal On Discrete Mathematics (SIDMA) publishes research articles on a broad range of topics from pure and applied mathematics, including combinatorics and graph theory, discrete optimization and operations research, to theoretical computer science, and coding and communication theory.

SIAM Journal on Computing (SICOMP) aims to provide coverage of the most significant work going on in the mathematical and formal aspects of computer science and nonnumerical computing. Submissions must be clearly written and make a significant technical contribution.

Multiscale Modeling & Simulation
SIAM J. on Applied Algebra and Geometry
SIAM J. on Applied Dynamical Systems
SIAM J. on Applied Mathematics
SIAM J. on Computing
SIAM J. on Control and Optimization
SIAM J. on Discrete Mathematics
SIAM J. on Financial Mathematics
SIAM J. on Imaging Sciences
SIAM J. on Mathematical Analysis
SIAM J. on Matrix Analysis and Applications
SIAM J. on Numerical Analysis
SIAM J. on Optimization
SIAM J. on Scientific Computing
SIAM/ASA J. on Uncertainty Quantification
SIAM Review
Theory of Probability & Its Applications

General Opportunities

We know it can be overwhelming to keep track of career opportunities that may be relevant to you as a member of the SIAM community. So, we’ve compiled lists of some of our favorite fellowship, internship, and research opportunities. Check ‘em out!

Fellowships

Looking for financial support to further your research? Fellowships often provide funding plus experiential learning opportunities to young researchers. Learn more about fellowship opportunities.

Internships allow you to network and forge connections for future job possibilities, while also exploring possible areas of interest. Look at this list of companies who offer valuable opportunities.

Our community is founded on igniting groundbreaking developments in applied math and computational science. Take a deeper dive into your area of study with one of these opportunities.