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 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 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 Shuichi Hirahara SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-349-FOCS18-382, December 2023. Abstract. There are significant obstacles to establishing an equivalence between the worst-case and average-case hardness of [math]....

By Elette Boyle, Vincent Cohen-Addad, Alexandra Kolla, and Mikkel Thorup SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-i-FOCS18-i, December 2023.

By Marcel Dall’Agnol, Tom Gur, and Oded Lachish SIAM Journal on Computing, Volume 52, Issue 6, Page 1413-1463, December 2023. Abstract. We prove a general structural theorem for a wide family of local algorithms, which includes property...

By Jesper Nederlof, Jakub Pawlewicz, Céline M. F. Swennenhuis, and Karol Węgrzycki SIAM Journal on Computing, Volume 52, Issue 6, Page 1369-1412, December 2023. Abstract. In the Bin Packing problem one is given [math] items with weights [math] and [math] bins...

By Noga Alon, Ehud Friedgut, Gil Kalai, and Guy Kindler SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2717-2729, December 2023. Abstract. Lionel Levine’s hat challenge has [math] players, each with a (very large or infinite) stack...

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 Dror Chawin and Ishay Haviv SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2670-2688, December 2023. Abstract. The orthogonality dimension of a graph [math] over [math] is the smallest integer [math] for...

By Andrzej Grzesik, Daniel Il’kovič, Bartłomiej Kielak, and Daniel Král’ SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2689-2716, December 2023. Abstract. An oriented graph [math] is quasirandom-forcing if the limit (homomorphism) density of [math] in a...

By Benny Applebaum and Eliran Kachlon SIAM Journal on Computing, Volume 52, Issue 6, Page 1321-1368, December 2023. Abstract. Suppose that you wish to sample a random graph [math] over [math] vertices and [math] edges...

By Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2626-2669, December 2023. Abstract. For a positive integer [math], a graph [math] is said to be [math]-closed if every...

By Amin Bahmanian SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2617-2625, December 2023. Abstract. Can we color the [math] cells of an [math] cube [math] with [math] colors in...

By Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2585-2616, December 2023. Abstract. One of the open problems in machine learning is whether any set-family of VC-dimension [math]...

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 R. Brignall and D. Cocks SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2558-2584, December 2023. Abstract. We create a framework for hereditary graph classes [math] built on a two-dimensional grid of...

By Barnabás Janzer, J. Robert Johnson, and Imre Leader SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2544-2557, December 2023. Abstract. How many random transpositions (meaning that we swap given pairs of elements with given probabilities...

By Melissa M. Fuentes SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2523-2543, December 2023. Abstract. We consider a problem proposed by Linial and Wilf to determine the structure of graphs...

By Xiutao Zhu, Ervin Györi, Zhen He, Zequn Lv, Nika Salia, Casey Tompkins, and Kitti Varga SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2508-2522, December 2023. Abstract. Let [math] denote the maximum number of edges not contained in any monochromatic copy of...

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 Ahmad Abdi, Gérard Cornuéjols, and Michael Zlatin SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2417-2461, December 2023. Abstract. Let [math] be a digraph. A dicut is a cut [math] for some nonempty proper...

By Yongtao Li and Yuejian Peng SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2462-2485, December 2023. Abstract. A well-known result in extremal spectral graph theory, known as Nosal’s theorem, states that if...

By Xiaolan Hu and Xing Peng SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2486-2507, December 2023. Abstract. For a simple graph [math], let [math] be the fractional chromatic number of [math]. In...

By Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, and Jacques Verstraëte SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2397-2416, December 2023. Abstract. We study the extremal number for paths in [math]-uniform hypergraphs where two consecutive edges of...

By Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2332-2364, December 2023. Abstract. A linkage in a graph [math] of size [math] is a subgraph [math] of [math]...

By Xin Ren and Kohji Yanagawa SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2382-2396, December 2023. Abstract. For a partition [math] of [math], the Specht ideal [math] is the ideal generated by...

By Reza Naserasr and Weiqiang Yu SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2365-2381, December 2023. Abstract. We define the signature packing number of a signed graph [math], denoted [math], to be...

By Paul Jungeblut, Laura Merker, and Torsten Ueckerdt SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2312-2331, December 2023. Abstract. The page number of a directed acyclic graph [math] is the minimum [math] for which...

By Matias Korman, André van Renssen, Marcel Roeloffzen, and Frank Staals SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2276-2311, December 2023. Abstract. We study the geodesic Voronoi diagram of a set [math] of [math] linearly moving sites...

By Dániel Gerbner SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2265-2275, December 2023. Abstract. The profile vector of a family [math] of subsets of an [math]-element set is [math],...

By Esther Galby, Liana Khazaliya, Fionn Mc Inerney, Roohani Sharma, and Prafullkumar Tale SIAM Journal on Discrete Mathematics, Volume 37, Issue 4, Page 2241-2264, December 2023. Abstract. For a graph [math], a subset [math] is called a resolving set if for any...

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 Mika Göös and Aviad Rubinstein SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-316-FOCS18-348, December 2023. We prove an $N^{2-o(1)}$ lower bound on the randomized communication complexity of finding an $\epsilon$-approximate Nash equilibrium...

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 Josh Alman and Virginia Vassilevska Williams SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-285-FOCS18-315, December 2023. We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser...

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 Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-250-FOCS18-284, December 2023. We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are...

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

By Akash Kumar, C. Seshadhri, and Andrew Stolman SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-216-FOCS18-249, December 2023. Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and...

By Urmila Mahadev SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-189-FOCS18-215, December 2023. We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme...

By Jatin Batra, Naveen Garg, and Amit Kumar SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-158-FOCS18-188, December 2023. In the weighted flow-time problem on a single machine, we are given a set of $n$ jobs,...

By Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing Wang SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-85-FOCS18-157, December 2023. We develop a framework for graph sparsification and sketching, based on a new tool, short cycle decomposition,...

By Vera Traub and Jens Vygen SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-37-FOCS18-84, December 2023. Among various variants of the traveling salesman problem (TSP), the $s$-$t$-path graph TSP has the special...

By Martin Grohe, Daniel Neuen, and Pascal Schweitzer SIAM Journal on Computing, Volume 52, Issue 6, Page FOCS18-1-FOCS18-36, December 2023. In a recent breakthrough, Babai [Proceedings of STOC, ACM, New York, 2016, pp. 684--697] gave a quasipolynomial-time...

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.