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.
Las Vegas, NV, United States
By Mika Göös, Alexandros Hollender, Siddhartha Jain, Gilbert Maystre, William Pires, Robert Robere, and Ran TaoSIAM Journal on Computing, Volume 53, Issue 3, Page 573-587, June 2024. Abstract. We show [math]. Here the class [math] consists of all total search problems that reduce to...
By Kristóf Bérczi, Endre Boros, and Kazuhisa MakinoSIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1417-1437, June 2024. Abstract. Horn functions form a subclass of Boolean functions possessing interesting structural and computational properties. These...
By Anqi Li and Lisa SauermannSIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1409-1416, June 2024. Abstract. In this paper, we strengthen a result by Green about an analogue of Sárközy’s theorem in...
By Noga Alon, Dor Elboim, János Pach, and Gábor TardosSIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1381-1408, June 2024. Abstract. It is known that any open necklace with beads of [math] types, in which the number...
By Patrick Bennett and Alan FriezeSIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1369-1380, June 2024. Abstract. We estimate the likely values of the chromatic and independence numbers of the random [math]-uniform [math]-regular...
By Maria Dascălu and Annie RaymondSIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1351-1368, June 2024. Abstract. Many important problems in extremal combinatorics can be stated as certifying polynomial inequalities in graph...
By Laurent Bulteau, Konrad K. Dabrowski, Noleen Köhler, Sebastian Ordyniak, and Daniël PaulusmaSIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1315-1350, June 2024. Abstract. A homomorphism [math] from a guest graph [math] to a host graph [math] is locally...
By Artur Czumaj and Christian SohlerSIAM Journal on Computing, Volume 53, Issue 2, Page 524-571, April 2024. Abstract. Let [math] be an [math]-point metric space. We assume that [math] is given in the distance...
By John FernleySIAM Journal on Discrete Mathematics, Volume 38, Issue 2, Page 1285-1314, June 2024. Abstract. The voter model is a classical interacting particle system, modeling how global consensus is formed...
By Michael A. Bender, Alex Conway, Martín Farach-Colton, Hanna Komlós, William Kuszmaul, and Nicole WeinSIAM 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 YuSIAM 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 XuSIAM 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 NoguchiSIAM 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 OgdenSIAM 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 NikolovSIAM 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 KavithaSIAM 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 TalSIAM 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 MichelSIAM 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 ZhangSIAM 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 TancerSIAM 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 SpirklSIAM 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 WoottersSIAM 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 ZamaraevSIAM 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 KamtueSIAM 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 StollenwerkSIAM 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 TompkinsSIAM 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 LenzenSIAM 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 HavivSIAM 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 BodwinSIAM 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. WoodSIAM 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 RothSIAM 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. VoudourisSIAM 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óthSIAM 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 SzpankowskiSIAM 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. WoodSIAM 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 ShiromaSIAM 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 YaoSIAM 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 Joshua Brakensiek and Sami DaviesSIAM 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 Robert AndrewsSIAM 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łatSIAM 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 YangSIAM 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 TurcotteSIAM 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 SvenssonSIAM 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 Marcin Briański, Gwenaël Joret, and Michał T. SewerynSIAM 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 ChenSIAM 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 LiuSIAM 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 Andreas Björklund, Thore Husfeldt, and Petteri KaskiSIAM 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 Pavol Hell, Jing Huang, and Jephian C.-H. LinSIAM 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 SpieksmaSIAM 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 SchneiderSIAM 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 WeckbeckerSIAM 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 TanigawaSIAM 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 StreibSIAM 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 TheadoSIAM 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 GrzesikSIAM 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. SpirklSIAM 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 LefmannSIAM 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 LiuSIAM 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 ZouSIAM 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 SylvesterSIAM 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 PierronSIAM 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 NeuenSIAM 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 LeeSIAM 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 WagnerSIAM 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 MehalelSIAM 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 WeckbeckerSIAM 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 SchulzSIAM 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 WilmerSIAM 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 MaSIAM 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. SawhneySIAM 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 MelnichenkoSIAM 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 ZamaraevSIAM 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. NguyenSIAM 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 SudakovSIAM 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 SchwarczSIAM 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éaSIAM 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ömSIAM 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 SchmandSIAM 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 MelbourneSIAM 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 FluckSIAM 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 MooreSIAM 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 YusterSIAM 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 RollinSIAM 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 XuSIAM 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 KwonSIAM 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 SunSIAM 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 MaoSIAM 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 KorhonenSIAM 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 YogevSIAM 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 VigodaSIAM 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 KothariSIAM 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 PengSIAM 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 ZenklusenSIAM 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 HollenderSIAM 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 SinglaSIAM 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 KhannaSIAM 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 ZuzicSIAM 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 IlangoSIAM 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 SrivastavaSIAM 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émorSIAM 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 LucierSIAM 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 SurianarayananSIAM 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 SidfordSIAM 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 WellnitzSIAM 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 MiltzowSIAM 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 SolomonSIAM 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 WeinsteinSIAM 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 ChenSIAM 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 WoottersSIAM 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 RezaeiSIAM 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 BreslerSIAM 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 GharanSIAM 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 MontanariSIAM 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...
Moscow, ID, United States
Hong Kong
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.
~*Learn More*~
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.
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.
Looking for financial support to further your research? Fellowships often provide funding plus experiential learning opportunities to young researchers. Learn more about fellowship opportunities.
Read More
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.