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 Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein SIAM Journal on Computing, Ahead of Print. Abstract. The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal...

By Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu SIAM Journal on Computing, Ahead of Print. Abstract. We give an almost quadratic [math] lower bound on the space usage of any [math]-pass streaming algorithm solving the (directed) [math]-[math]...

By Zichao Dong and Zijian Xu SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1269-1284, June 2024. Abstract. We prove that every family of (not necessarily distinct) even cycles [math] on some fixed...

By Kenta Noguchi SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1250-1268, June 2024. Abstract. We completely characterize the triangulations of the projective plane that admit a spanning bipartite quadrangulation...

By Natalie Behague, Tom Johnston, Shoham Letzter, Natasha Morrison, and Shannon Ogden SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1239-1249, June 2024. Abstract. Given a graph [math], we say that an edge-colored graph [math] is [math]-rainbow saturated if...

By Lily Li and Aleksandar Nikolov SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1222-1238, June 2024. Abstract. The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp....

By Telikepalli Kavitha SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1202-1221, June 2024. Abstract. Let [math] be a bipartite graph where every node has a strict ranking of its...

By Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal SIAM Journal on Computing, Volume 53, Issue 2, Page 480-523, April 2024. Abstract. We introduce a variant of Probabilistically Checkable Proofs (PCPs) that we refer to as rectangular PCPs,...

By Bryce Frederickson and Lukas Michel SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1193-1201, June 2024. Abstract. Given a simple Eulerian binary matroid [math], what is the minimum number of disjoint circuits...

By Benjamin Bergougnoux and Mamadou M. Kanté SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1191-1192, March 2024. Abstract. We spotted an error in our publication More applications of the d-neighbor equivalence: Acyclicity and...

By Sepehr Assadi, Gillat Kol, and Zhijun Zhang SIAM Journal on Computing, Ahead of Print. Abstract. We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There...

By Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer SIAM Journal on Computing, Volume 53, Issue 2, Page 431-479, April 2024. Abstract. Deciding whether a diagram of a knot can be untangled with a given number of moves...

By Sepehr Hajebi, Yanjia Li, and Sophie Spirkl SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1158-1190, March 2024. Abstract. The List-3-Coloring Problem is to decide, given a graph [math] and a list [math] of...

By Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters SIAM Journal on Computing, Volume 53, Issue 2, Page 389-430, April 2024. Abstract. This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the...

By Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev SIAM Journal on Computing, Volume 53, Issue 2, Page 346-388, April 2024. Abstract. A graph whose edges only appear at certain points in time is called a temporal graph...

By Pakawut Jiradilok and Supanat Kamtue SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1113-1157, March 2024. Abstract. In the infinite regular tree [math] with [math], we consider families [math], indexed by vertices...

By Sjoerd Dirksen, Shahar Mendelson, and Alexander Stollenwerk SIAM Journal on Computing, Volume 53, Issue 2, Page 315-345, April 2024. Abstract. We consider the problem of embedding a subset of [math] into a low-dimensional Hamming cube in...

By Debsoumya Chakraborti, Kevin Hendrey, Ben Lund, and Casey Tompkins SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1090-1112, March 2024. Abstract. We call an edge-colored graph rainbow if all of its edges receive distinct colors. An...

By Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole Wein SIAM Journal on Computing, Ahead of Print. Abstract. The online list-labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal...

By Lijie Chen, Gillat Kol, Dmitry Paramonov, Raghuvansh R. Saxena, Zhao Song, and Huacheng Yu SIAM Journal on Computing, Ahead of Print. Abstract. We give an almost quadratic [math] lower bound on the space usage of any [math]-pass streaming algorithm solving the (directed) [math]-[math]...

By Zichao Dong and Zijian Xu SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1269-1284, June 2024. Abstract. We prove that every family of (not necessarily distinct) even cycles [math] on some fixed...

By Kenta Noguchi SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1250-1268, June 2024. Abstract. We completely characterize the triangulations of the projective plane that admit a spanning bipartite quadrangulation...

By Natalie Behague, Tom Johnston, Shoham Letzter, Natasha Morrison, and Shannon Ogden SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1239-1249, June 2024. Abstract. Given a graph [math], we say that an edge-colored graph [math] is [math]-rainbow saturated if...

By Lily Li and Aleksandar Nikolov SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1222-1238, June 2024. Abstract. The determinant lower bound of Lovász, Spencer, and Vesztergombi [European J. Combin., 7 (1986), pp....

By Telikepalli Kavitha SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1202-1221, June 2024. Abstract. Let [math] be a bipartite graph where every node has a strict ranking of its...

By Amey Bhangale, Prahladh Harsha, Orr Paradise, and Avishay Tal SIAM Journal on Computing, Volume 53, Issue 2, Page 480-523, April 2024. Abstract. We introduce a variant of Probabilistically Checkable Proofs (PCPs) that we refer to as rectangular PCPs,...

By Bryce Frederickson and Lukas Michel SIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1193-1201, June 2024. Abstract. Given a simple Eulerian binary matroid [math], what is the minimum number of disjoint circuits...

By Benjamin Bergougnoux and Mamadou M. Kanté SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1191-1192, March 2024. Abstract. We spotted an error in our publication More applications of the d-neighbor equivalence: Acyclicity and...

By Sepehr Assadi, Gillat Kol, and Zhijun Zhang SIAM Journal on Computing, Ahead of Print. Abstract. We consider the problem of finding a maximal independent set (MIS) in the shared blackboard communication model with vertex-partitioned inputs. There...

By Clément Legrand-Duchesne, Ashutosh Rai, and Martin Tancer SIAM Journal on Computing, Volume 53, Issue 2, Page 431-479, April 2024. Abstract. Deciding whether a diagram of a knot can be untangled with a given number of moves...

By Sepehr Hajebi, Yanjia Li, and Sophie Spirkl SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1158-1190, March 2024. Abstract. The List-3-Coloring Problem is to decide, given a graph [math] and a list [math] of...

By Zeyu Guo, Ray Li, Chong Shangguan, Itzhak Tamo, and Mary Wootters SIAM Journal on Computing, Volume 53, Issue 2, Page 389-430, April 2024. Abstract. This paper shows that there exist Reed–Solomon (RS) codes, over exponentially large finite fields in the...

By Arnaud Casteigts, Michael Raskin, Malte Renken, and Viktor Zamaraev SIAM Journal on Computing, Volume 53, Issue 2, Page 346-388, April 2024. Abstract. A graph whose edges only appear at certain points in time is called a temporal graph...

By Pakawut Jiradilok and Supanat Kamtue SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1113-1157, March 2024. Abstract. In the infinite regular tree [math] with [math], we consider families [math], indexed by vertices...

By Sjoerd Dirksen, Shahar Mendelson, and Alexander Stollenwerk SIAM Journal on Computing, Volume 53, Issue 2, Page 315-345, April 2024. Abstract. We consider the problem of embedding a subset of [math] into a low-dimensional Hamming cube in...

By Debsoumya Chakraborti, Kevin Hendrey, Ben Lund, and Casey Tompkins SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1090-1112, March 2024. Abstract. We call an edge-colored graph rainbow if all of its edges receive distinct colors. An...

By Ruben Becker, Yuval Emek, Mohsen Ghaffari, and Christoph Lenzen SIAM Journal on Computing, Volume 53, Issue 2, Page 247-286, April 2024. Abstract. We study the problem of approximating the distances in an undirected weighted graph [math] by the...

By Ishay Haviv SIAM Journal on Computing, Volume 53, Issue 2, Page 287-314, April 2024. Abstract. The Kneser graph [math] is defined for integers [math] and [math] with [math] as the graph...

By Amir Abboud and Greg Bodwin SIAM Journal on Computing, Volume 53, Issue 2, Page 221-246, April 2024. Abstract. We define and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work...

By Robert Hickingbotham and David R. Wood SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1057-1089, March 2024. Abstract. The planar graph product structure theorem of Dujmović et al. [J. ACM, 67 (2020), 22] states that...

By Jacob Focke and Marc Roth SIAM Journal on Computing, Volume 53, Issue 2, Page 189-220, April 2024. Abstract. We study the computational complexity of the problem [math] of counting [math]-vertex induced subgraphs of a...

By Georgios Amanatidis, Georgios Birmpas, Aris Filos-Ratsikas, and Alexandros A. Voudouris SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1007-1029, March 2024. Abstract. In most social choice settings, the participating agents express their preferences over the different alternatives...

By Sujoy Bhore, Arnold Filtser, Hadi Khodabandeh, and Csaba D. Tóth SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1030-1056, March 2024. Abstract. Given a metric space [math], a weighted graph [math] over [math] is a metric [math]-spanner...

By Alan M. Frieze, Krzysztof Turowski, and Wojciech Szpankowski SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 988-1006, March 2024. Abstract. We present a rigorous and precise analysis of the maximum degree and the average degree...

By Robert Hickingbotham, Freddie Illingworth, Bojan Mohar, and David R. Wood SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 965-987, March 2024. Abstract. A circle graph is an intersection graph of a set of chords of a circle....

By Catherine Babecki and David Shiroma SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 947-964, March 2024. Abstract. We show that the eigenpolytopes of graphs are universal in the sense that every polytope,...

By Yen-Jen Cheng, Sen-Peng Eu, Tung-Shan Fu, and Jyun-Cheng Yao SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 917-946, March 2024. Abstract. For a finite Coxeter group [math], Josuat-Vergès derived a [math]-polynomial counting the maximal chains in...

By Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong SIAM Journal on Computing, Volume 53, Issue 1, Page 146-187, February 2024. Abstract. This is the second paper in a series of two. The goal of the series is to...

By Joshua Brakensiek and Sami Davies SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 883-916, March 2024. Abstract. Since the seminal result of Karger, Motwani, and Sudan, algorithms for approximate 3-coloring have primarily...

By Maria Chudnovsky, Sophie Spirkl, and Mingxian Zhong SIAM Journal on Computing, Volume 53, Issue 1, Page 111-145, February 2024. Abstract. This is the first paper in a series whose goal is to give a polynomial-time algorithm...

By Robert Andrews SIAM Journal on Computing, Ahead of Print. Abstract. We show that lower bounds on the border rank of matrix multiplication can be used to nontrivially derandomize polynomial identity testing for...

By Deepak Bal, Alan Frieze, and Paweł Prałat SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 867-882, March 2024. Abstract. Given a graph [math] on [math] vertices and an assignment of colors to its edges,...

By Siqi Liu, Sidhanth Mohanty, Tselil Schramm, and Elizabeth Yang SIAM Journal on Computing, Ahead of Print. Abstract. The random geometric graph model [math] is a distribution over graphs in which the edges capture a latent geometry. To sample...

By Maria Chudnovsky, Sergey Norin, Paul D. Seymour, and Jérémie Turcotte SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 845-856, March 2024. Abstract. We prove that every connected [math]-free graph has cop number at most two, solving a...

By Nikhil Bansal, Lars Rohwedder, and Ola Svensson SIAM Journal on Computing, Ahead of Print. Abstract. We relate discrepancy theory with the classic scheduling problems of minimizing max flow time and total flow time on unrelated machines....

By Janardhan Kulkarni, Yang P. Liu, Ashwin Sah, Mehtaab S. Sawhney, and Jakub Tarnawski SIAM Journal on Computing, Volume 53, Issue 1, Page 87-110, February 2024. Abstract. We give an online algorithm that with high probability computes a [math] edge coloring on a...

By Marcin Briański, Gwenaël Joret, and Michał T. Seweryn SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 857-866, March 2024. Abstract. The circumference of a graph [math] with at least one cycle is the length of...

By Lijie Chen SIAM Journal on Computing, Ahead of Print. Abstract. Following the seminal work of [R. R. Williams, J. ACM, 61 (2014)], in a recent breakthrough, [C. D. Murray and R....

By Jerry Li and Allen Liu SIAM Journal on Computing, Ahead of Print. Abstract. We consider the problem of clustering mixtures of mean-separated Gaussians in high dimensions. We are given samples from a mixture of...

By Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan Thomassé SIAM Journal on Computing, Volume 53, Issue 1, Page 47-86, February 2024. Abstract. In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent...

By Andreas Björklund, Thore Husfeldt, and Petteri Kaski SIAM Journal on Computing, Ahead of Print. Abstract. Given a directed graph as input, we show how to efficiently find a shortest (directed, simple) cycle on an even number...

By David Gamarnik, Aukosh Jagannath, and Alexander S. Wein SIAM Journal on Computing, Volume 53, Issue 1, Page 1-46, February 2024. Abstract. We consider the problem of finding nearly optimal solutions of optimization problems with random objective functions....

By Pavol Hell, Jing Huang, and Jephian C.-H. Lin SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 828-844, March 2024. Abstract. We introduce the class of strong cocomparability graphs, as the class of reflexive graphs whose...

By Mark de Berg, Arpan Sadhukhan, and Frits Spieksma SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 790-827, March 2024. Abstract. Let [math] be a set of points in [math], where each point [math] has an...

By Rad Niazadeh, Renato Paes Leme, and Jon Schneider SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 726-742, March 2024. Abstract. We construct explicit combinatorial Bernoulli factories for the following class of flow-based polytopes: integral 0/1-polytopes...

By Yann Disser, Max Klimm, Annette Lutz, and David Weckbecker SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 764-789, March 2024. Abstract. We consider the problem of maximizing a fractionally subadditive function under an increasing knapsack constraint....

By James Cruickshank, Fatemeh Mohammadi, Harshit J. Motwani, Anthony Nixon, and Shin-ichi Tanigawa SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 743-763, March 2024. Abstract. We consider the global rigidity problem for bar-joint frameworks where each vertex is constrained to...

By Sarah Miracle and Amanda Pascoe Streib SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 702-725, March 2024. Abstract. In this paper, we study a biased version of the nearest-neighbor transposition Markov chain on...

By Brendan Nagle and John Theado SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 668-701, March 2024. Abstract. Szemerédi’s regularity lemma guarantees that, for fixed [math], every graph [math] admits an [math]-regular and...

By Sebastian Babiński and Andrzej Grzesik SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 629-644, March 2024. Abstract. In 1959, Erdős and Gallai proved the asymptotically optimal bound for the maximum number of...

By Alex Scott, Paul Seymour, and Sophie T. Spirkl SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 645-667, March 2024. Abstract. Fix [math], and let [math] be a graph, with vertex set partitioned into [math] subsets...

By Maria Axenovich and Hanno Lefmann SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 609-628, March 2024. Abstract. Hindman proved in 1979 that no matter how natural numbers are colored in [math] colors,...

By Lele Liu SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 590-608, March 2024. Abstract. We prove two conjectures in spectral extremal graph theory involving the linear combinations of graph...

By Michel Habib, Lalla Mouatadid, Éric Sopena, and Mengchuan Zou SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 566-589, March 2024. Abstract. Modular decomposition focuses on repeatedly identifying a module [math] (a collection of vertices that shares...

By Dimitrios Los, Thomas Sauerwald, and John Sylvester SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 529-565, March 2024. Abstract. We introduce a new class of balanced allocation processes which are primarily characterized by “filling”...

By Nicolas Bousquet, Quentin Deschamps, Lucas De Meyer, and Théo Pierron SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 504-528, March 2024. Abstract. The discharging method is a powerful proof technique, especially for graph coloring problems. Its major...

By Daniel Neuen SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 453-484, March 2024. Abstract. We present an isomorphism test for graphs of Euler genus [math] running in time [math]....

By Steffen Borgwardt, Weston Grewe, and Jon Lee SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 485-503, March 2024. Abstract. The investigation of combinatorial diameters of polyhedra is a classical topic in linear programming due...

By Steven Kelk, Ruben Meuwese, and Stephan Wagner SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 380-411, March 2024. Abstract. Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species (“taxa”),...

By Yuval Filmus and Idan Mehalel SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 412-452, March 2024. Abstract. In the distributional Twenty Questions game, Bob chooses a number [math] from 1 to [math]...

By Yann Disser and David Weckbecker SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 348-379, March 2024. Abstract. We consider classes of objective functions of cardinality-constrained maximization problems for which the greedy algorithm...

By Philipp Hieronymi and Chris Schulz SIAM Journal on Computing, Ahead of Print. Abstract. Let [math] be two multiplicatively independent integers. Cobham’s famous theorem states that a set [math] is both [math]-recognizable and [math]-recognizable if...

By Noga Alon, Emil Powierski, Michael Savery, Alex Scott, and Elizabeth Wilmer SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 327-347, March 2024. Abstract. For an oriented graph [math] and a set [math], the inversion of [math] in [math]...

By Hao Chen and Jie Ma SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 316-326, March 2024. Abstract. A graph [math] is called common and, respectively, strongly common if the number of monochromatic...

By Ryan Alweiss, Yang P. Liu, and Mehtaab S. Sawhney SIAM Journal on Computing, Ahead of Print. Abstract. We study discrepancy minimization for vectors in [math] under various settings. The main result is the analysis of a new simple...

By Davide Bilò, Tobias Friedrich, Pascal Lenzner, and Anna Melnichenko SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 277-315, March 2024. Abstract. Network creation games are a well-known approach for explaining and analyzing the structure, quality, and...

By Bogdan Alecu, Vadim V. Lozin, Daniel A. Quiroz, Roman Rabinovich, Igor Razgon, and Viktor Zamaraev SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 261-276, March 2024. Abstract. Given two [math]-vertex graphs [math] and [math] of bounded treewidth, is there an [math]-vertex graph...

By Tung H. Nguyen SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 243-260, March 2024. Abstract. For integers [math] and [math], let [math] be the least integer [math] such that every...

By Domagoj Bradač, Lior Gishboliner, and Benny Sudakov SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 225-242, March 2024. Abstract. In this paper we prove several results on Ramsey numbers [math] for a fixed graph...

By Kristóf Bérczi and Tamás Schwarcz SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 132-147, March 2024. Abstract. The basis exchange axiom has been a driving force in the development of matroid theory....

By Mikhael Carmona, Victor Chepoi, Guyslain Naves, and Pascal Préa SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 190-224, March 2024. Abstract. A Robinson space is a dissimilarity space [math] (i.e., a set [math] of size [math]...

By Eun Jung Kim, Tomáš Masařík, Marcin Pilipczuk, Roohani Sharma, and Magnus Wahlström SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 170-189, March 2024. Abstract. One of the first applications of the recently introduced technique of flow augmentation [Kim et...

By Martin Hoefer, Kevin Schewior, and Daniel Schmand SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 148-169, March 2024. Abstract. We consider a selection problem with stochastic probing. There is a set of items whose...

By Abdulmajeed Alqasem, Heshan Aravinda, Arnaud Marsiglietti, and James Melbourne SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 93-102, March 2024. Abstract. A remarkable conjecture of Feige [SIAM J. Comput., 35 (2006), pp. 964–984] asserts that for...

By Eva Fluck SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 75-92, March 2024. Abstract. We establish a connection between tangles, a concept from structural graph theory that plays a...

By Dmitriy Kunisky and Cristopher Moore SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 103-131, March 2024. Abstract. Grigoriev (2001) and Laurent (2003) independently showed that the sum-of-squares hierarchy of semidefinite programs does...

By Raphael Yuster SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 43-54, March 2024. Abstract. For every fixed [math], it is proved that if an [math]-vertex directed graph has at...

By Simona Boyadzhiyska, Dennis Clemens, Pranshu Gupta, and Jonathan Rollin SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 55-74, March 2024. Abstract. A graph [math] is Ramsey for a pair of graphs [math] if any red/blue-coloring of...

By Joseph Paat, Ingo Stallknecht, Zach Walsh, and Luze Xu SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 1-18, March 2024. Abstract. An integer matrix [math] is [math]-modular if the determinant of each [math] submatrix of [math]...

By Tony Huynh and O-joung Kwon SIAM Journal on Discrete Mathematics, Volume 38, Issue 1, Page 19-42, March 2024. Abstract. We prove that there exists a function [math] such that for every [math]-free graph [math]...

By Aviad Rubinstein, Saeed Seddighin, Zhao Song, and Xiaorui Sun SIAM Journal on Computing, Ahead of Print. Abstract. Longest common subsequence (LCS) is a classic and central problem in combinatorial optimization. While LCS admits a quadratic time solution, recent...

By Xiao Mao SIAM Journal on Computing, Ahead of Print. Abstract. The (unweighted) tree edit distance problem for [math] node trees asks to compute a measure of dissimilarity between two rooted trees...

By Tuukka Korhonen SIAM Journal on Computing, Ahead of Print. Abstract. We give an algorithm that, given an [math]-vertex graph [math] and an integer [math], in time [math] either outputs a tree...

By Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev SIAM Journal on Computing, Ahead of Print. Abstract. Laws of large numbers guarantee that given a large enough sample from some population, the measure of any fixed subpopulation is...

By Zongchen Chen, Kuikui Liu, and Eric Vigoda SIAM Journal on Computing, Ahead of Print. Abstract. We prove an optimal mixing time bound for the single-site update Markov chain known as the Glauber dynamics or Gibbs sampling...

By Kaspars Balodis, Shalev Ben-David, Mika Göös, Siddhartha Jain, and Robin Kothari SIAM Journal on Computing, Ahead of Print. Abstract. We exhibit an unambiguous [math]-DNF (disjunctive normal form) formula that requires conjunctive normal form width [math], which is optimal up to...

By Yu Gao, Yang Liu, and Richard Peng SIAM Journal on Computing, Ahead of Print. Abstract. We give an algorithm for computing exact maximum flows on graphs with [math] edges and integer capacities in the range [math]...

By Federica Cecchetto, Vera Traub, and Rico Zenklusen SIAM Journal on Computing, Ahead of Print. Abstract. We consider the connectivity augmentation problem (CAP), a classical problem in the area of survivable network design. It is about increasing...

By Aris Filos-Ratsikas, Kristoffer A. Hansen, Kasper Høgh, and Alexandros Hollender SIAM Journal on Computing, Ahead of Print. Abstract. We introduce a new technique for proving membership of problems in FIXP: the class capturing the complexity of computing a fixed...

By Sepehr Assadi and Sahil Singla SIAM Journal on Computing, Ahead of Print. Abstract. A longstanding open problem in algorithmic mechanism design is to design truthful mechanisms that are computationally efficient and (approximately) maximize welfare...

By Deeparnab Chakrabarty, Yu Chen, and Sanjeev Khanna SIAM Journal on Computing, Ahead of Print. Abstract. Submodular function minimization (SFM) and matroid intersection are fundamental discrete optimization problems with applications in many fields. It is well known...

By Mohsen Ghaffari, Bernhard Haeupler, and Goran Zuzic SIAM Journal on Computing, Ahead of Print. Abstract. We prove the existence of an oblivious routing scheme that is [math]-competitive in terms of [math], thus resolving a well-known question...

By Rahul Ilango SIAM Journal on Computing, Ahead of Print. Attempts to prove the intractability of the Minimum Circuit Size Problem ($\mathsf{MCSP}$) date as far back as the 1950s and are well...

By Jingcheng Liu, Alistair Sinclair, and Piyush Srivastava SIAM Journal on Computing, Ahead of Print. We explore connections between the phenomenon of correlation decay (more precisely, strong spatial mixing) and the location of Lee--Yang and Fisher zeros...

By Shai Evra, Tali Kaufman, and Gilles Zémor SIAM Journal on Computing, Ahead of Print. Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been...

By Paul Dütting, Thomas Kesselheim, and Brendan Lucier SIAM Journal on Computing, Ahead of Print. Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight....

By Daniel Lokshtanov, Saket Saurabh, and Vaishali Surianarayanan SIAM Journal on Computing, Ahead of Print. In the Min $k$-Cut problem, the input consists of an edge weighted graph $G$ and an integer $k$, and the task is...

By Tarun Kathuria, Yang P. Liu, and Aaron Sidford SIAM Journal on Computing, Ahead of Print. We present an algorithm which given any $m$-edge directed graph with positive integer capacities at most $U$, vertices $a$ and $b$,...

By Marc Roth, Johannes Schmitt, and Philip Wellnitz SIAM Journal on Computing, Ahead of Print. Given a graph property $\Phi$, the problem $\#\ensuremath{{\sc IndSub}}(\Phi)$ asks, on input of a graph $G$ and a positive integer $k$, to...

By Jeff Erickson, Ivor van der Hoog, and Tillmann Miltzow SIAM Journal on Computing, Ahead of Print. We study algorithmic problems that belong to the complexity class of the existential theory of the reals ($\exists \mathbb{R}$). A problem is...

By Hung Le and Shay Solomon SIAM Journal on Computing, Ahead of Print. Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 1980s...

By Alexander Golovnev, Gleb Posobin, Oded Regev, and Omri Weinstein SIAM Journal on Computing, Ahead of Print. Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early...

By Josh Alman and Lijie Chen SIAM Journal on Computing, Ahead of Print. For a matrix $H$ over a field $\mathbb{F}$, its rank-$r$ rigidity, denoted by $\mathscr{R}_{H}(r)$, is the minimum Hamming distance from $H$ to...

By Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters SIAM Journal on Computing, Ahead of Print. We show that Gallager's ensemble of low-density parity-check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes...

By Nima Anari and Alireza Rezaei SIAM Journal on Computing, Ahead of Print. We prove that the permanent of nonnegative matrices can be deterministically approximated within a factor of $\sqrt{2}^n$ in polynomial time, improving upon...

By Enric Boix-Adserà, Matthew Brennan, and Guy Bresler SIAM Journal on Computing, Ahead of Print. We consider the problem of counting $k$-cliques in $s$-uniform Erdös--Rényi hypergraphs $G(n,c,s)$ with edge density $c$ and show that its fine-grained average-case...

By Nima Anari, Kuikui Liu, and Shayan Oveis Gharan SIAM Journal on Computing, Ahead of Print. We say a probability distribution $\mu$ is spectrally independent if an associated pairwise influence matrix has a bounded largest eigenvalue for the...

By Andrea Montanari SIAM Journal on Computing, Ahead of Print. Let ${A}\in{\mathbb R}^{n\times n}$ be a symmetric random matrix with independent and identically distributed (i.i.d.) Gaussian entries above the diagonal. We consider...

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

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.

Established in 2020, the prize is awarded every two years to an early career researcher for recent contributions in the field of applied and computational discrete algorithms.

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

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.

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

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.

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 MAA-SIAM-AMS Hrabowski-Gates-Tapia-McBay (HGTM) Lecture is named after four influential scientists of color: Freeman Hrabowski, President of the University of Maryland at Baltimore County; James S. Gates, University of Maryland, College Park; Richard Tapia, Rice University; and Shirley McBay, Founder and former President of Quality Education for Minorities. This lecture started in 2016 as an activity of the Mathematical Association of America’s Committee on Minority Participation and became a jointly sponsored MAA-SIAM-AMS event in 2018.

The prize recognizes students for outstanding solutions to real world math problems. It is awarded to six 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 Prize is not currently active. For the 20 years before it was discontinued in 2019, the SIAM Outstanding Paper Prizes brought attention to papers published in SIAM journals. Three awards were 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.

This activity group fosters research on the computational solution of combinatorial problems in areas including combinatorial scientific computing, algorithmic computer science, algorithm engineering, algorithmic differentiation, combinatorial optimization, and emerging applications. Drawing from academia, the national research labs, and industry, the activity group will bring together mathematicians, computer scientists, statisticians, scientists, and engineers to promote research in applied and computational combinatorics.

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.