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.

Upcoming Related Conferences

Upcoming Related Conferences

SIAM Symposium on Simplicity in Algorithms (SOSA20)

January 6 - 7, 2020 Salt Lake City, Utah, U.S. More Information

By Yi Li, Huy L. Nguyễn, and David P. Woodruff SIAM Journal on Computing, Volume 48, Issue 6, Page 1643-1697, January 2019. This paper presents a systematic study of the space complexity of estimating the Schatten $p$-norms of an...

By Elad Aigner-Horev and Yury Person SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2175-2180, January 2019. Given a dense subset $A$ of the first $n$ positive integers, we provide a short...

By Stephen Melczer and Mark C. Wilson SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2140-2174, January 2019. We consider the enumeration of walks on the nonnegative lattice $\mathbb{N}^{d},$ with steps defined by a...

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 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 Yi Li, Huy L. Nguyễn, and David P. Woodruff SIAM Journal on Computing, Volume 48, Issue 6, Page 1643-1697, January 2019. This paper presents a systematic study of the space complexity of estimating the Schatten $p$-norms of an...

By Elad Aigner-Horev and Yury Person SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2175-2180, January 2019. Given a dense subset $A$ of the first $n$ positive integers, we provide a short...

By Stephen Melczer and Mark C. Wilson SIAM Journal on Discrete Mathematics, Volume 33, Issue 4, Page 2140-2174, January 2019. We consider the enumeration of walks on the nonnegative lattice $\mathbb{N}^{d},$ with steps defined by a...

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

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.

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.

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.

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.

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.

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.

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.