Bonn, , Germany

Philadelphia, PA, United States

Houston, TX, United States

Albuquerque, NM, United States

Albuquerque, NM, United States

Honolulu, HI, United States

Northampton, MA, United States

IL, United States

By Mengyu Cao, Benjian Lv, Kaishun Wang, and Sanming Zhou
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1823-1847, January 2022.
Let $V$ be an $n$-dimensional vector space over a finite field $\mathbb{F}_q$. In this paper we...

Smithfield, RI, United States

PA, United States

Albuquerque, NM, United States

Albuquerque, NM, United States

By Margarita Akhmejanova and Maksim Zhukovskii
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1788-1799, January 2022.
In this paper, we disprove EMSO(FO$^2$) convergence law for the binomial random graph $G(n,p)$ for any...

By Arpitha P. Bharathi and Monaldo Mastrolilli
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1800-1822, January 2022.
In this paper we examine polynomial ideals that are the vanishing ideals of solution sets of...

By Fabrizio Grandoni, Bundit Laekhanukit, and Shi Li
SIAM Journal on Computing, Ahead of Print.
In the directed Steiner tree (DST) problem, we are given an $n$-vertex directed edge-weighted graph, a root $r$, and a collection of...

By Sylvia Boyd, Joseph Cheriyan, Robert Cummings, Logan Grout, Sharat Ibrahimpur, Zoltán Szigeti, and Lu Wang
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1730-1747, January 2022.
Given a connected undirected graph $\overline{G}$ on $n$ vertices and nonnegative edge costs $c$, the $\ensuremath{{2ECM}}$...

By Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Yota Otachi
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1761-1787, January 2022.
Structural graph parameters, such as treewidth, pathwidth, and clique-width, are a central topic of study in...

By María A. Hernández Cifre and Eduardo Lucas
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1748-1760, January 2022.
The conjectured log-Brunn--Minkowski inequality says that the volume of centrally symmetric convex bodies $K,L\subset\mathbb{R}^n$ satisfies ${vol}\bigl((1-\lambda)\cdot...

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 Konrad Anand and Mark Jerrum
SIAM Journal on Computing, Volume 51, Issue 4, Page 1280-1295, January 2022.
We present a simple algorithm that perfectly samples configurations from the unique Gibbs measure of a spin...

By Urmila Mahadev
SIAM Journal on Computing, Volume 51, Issue 4, Page 1172-1229, January 2022.
We present the first protocol allowing a classical computer to interactively verify the result of an efficient...

By Alan M. Frieze, Wesley Pegden, and Tomasz Tkocz
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1687-1710, January 2022.
Let $p=\frac{1+\varepsilon}{n}$. It is known that if $N=\varepsilon^3n\to\infty$, then with high probability (w.h.p.) $G_{n,p}$ has a...

By Jonathan Tidor and Yufei Zhao
SIAM Journal on Computing, Volume 51, Issue 4, Page 1230-1279, January 2022.
We study the property testing of functions $\mathbb F_p^n\to[R]$ for fixed prime $p$ and positive integer $R$....

By Peter Nelson and Kazuhiro Nomoto
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1711-1729, January 2022.
A simple binary matroid is called $I_4$-free if none of its rank-4 flats are independent sets....

By Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, and Eran Omri
SIAM Journal on Computing, Volume 51, Issue 4, Page 1126-1171, January 2022.
In his seminal work, Cleve [Proceedings of the 18th Annual ACM Symposium on Theory of Computing, 1986,...

By Renato Paes Leme and Jon Schneider
SIAM Journal on Computing, Volume 51, Issue 4, Page 1096-1125, January 2022.
We study the problem of contextual search, a multidimensional generalization of binary search that captures many problems...

By Adam Blumenthal, Bernard Lidický, Ryan R. Martin, Sergey Norin, Florian Pfender, and Jan Volec
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1678-1686, January 2022.
The Hall ratio of a graph $G$ is the maximum value of $v(H) / \alpha(H)$ taken...

By Ian M. Wanless and David R. Wood
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1663-1677, January 2022.
The Lovász Local Lemma is a powerful probabilistic technique for proving the existence of combinatorial objects....

By Esther Ezra and Micha Sharir
SIAM Journal on Computing, Volume 51, Issue 4, Page 1065-1095, January 2022.
We consider several intersection searching problems that involve lines in ${\mathbb R}^3$ and present improved algorithms for...

By Hongliang Lu, Yan Wang, and Xingxing Yu
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1645-1662, January 2022.
Let $n$ be a sufficiently large integer with $n\equiv 0\pmod 4$, and let $F_i \subseteq{[n]\choose 4}$,...

By Lap Chi Lau and Hong Zhou
SIAM Journal on Computing, Volume 51, Issue 4, Page 1018-1064, January 2022.
We present a spectral approach to design approximation algorithms for network design problems. We observe that the...

By Rong Chen
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1627-1644, January 2022.
The class of quasi-graphic matroids, recently introduced by Geelen, Gerards, and Whittle, is minor closed and...

By Yahav Alon, Michael Krivelevich, and Peleg Michaeli
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1612-1626, January 2022.
We present an explicit connected spanning structure that appears in a random graph just above the...

By Lap Chi Lau and Hong Zhou
SIAM Journal on Computing, Volume 51, Issue 4, Page 900-951, January 2022.
We present a local search framework to design and analyze both combinatorial algorithms and rounding algorithms for...

By Anupam Gupta, Amit Kumar, and Debmalya Panigrahi
SIAM Journal on Computing, Volume 51, Issue 4, Page 975-1017, January 2022.
We consider two generalizations of the classical weighted paging problem that incorporate the notion of delayed service...

By Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer
SIAM Journal on Computing, Volume 51, Issue 4, Page 952-974, January 2022.
We present efficient differentially private algorithms for learning unions of polygons in the plane (which are not...

By Vincent Moulton and Taoyang Wu
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1586-1611, January 2022.
RNA molecules are single-stranded analogues of DNA that can fold into various structures which influence their...

By Holger Dell, John Lapinskas, and Kitty Meeks
SIAM Journal on Computing, Volume 51, Issue 4, Page 849-899, January 2022.
In this paper, we design efficient algorithms to approximately count the number of edges of a given...

By Michael Elkin and Ofer Neiman
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1529-1550, January 2022.
Given metric spaces $(X,d)$ and $(Y,\rho)$ and an ordering $x_1,x_2,\ldots,x_n$ of $(X,d)$, an embedding $f: X...

By Simona Boyadzhiyska, Dennis Clemens, and Pranshu Gupta
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1503-1528, January 2022.
Given any graph $H$, a graph $G$ is said to be $q$-Ramsey for $H$ if every...

By Luis Montejano, Jorge L. Ramírez Alfonsín, and Ivan Rasskin
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1551-1566, January 2022.
A self-dual map $G$ is said to be antipodally self-dual if the dual map $G^*$ is...

By Guyslain Naves and Bruce Shepherd
SIAM Journal on Discrete Mathematics, Volume 36, Issue 3, Page 1567-1585, January 2022.
Gomory--Hu (GH) trees are a classical sparsification technique for graph connectivity. For an edge-capacitated undirected graph...

By On-Hei Solomon Lo and Jianguo Qian
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1496-1501, June 2022.
Whitney proved in 1931 that every 4-connected planar triangulation is hamiltonian. Later, Hakimi, Schmeichel, and Thomassen...

By Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, and Christian Wulff-Nilsen
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-i-STOC20-i, June 2022.
This issue of SICOMP contains six specially selected papers from STOC 2020, the Fifty-second Annual ACM Symposium...

By József Balogh, Ryan R. Martin, Dániel T. Nagy, and Balázs Patkós
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1483-1495, June 2022.
For given posets $P$ and $Q$ and an integer $n$, the generalized Turán problem for posets...

By Naoyuki Kamiyama
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1467-1482, June 2022.
A super-stable matching is a solution concept in the variant of the stable matching problem in...

By S. Rasoul Etesami
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1436-1466, June 2022.
We consider an online assortment problem with $[n]=\{1,2,\ldots,n\}$ sellers, each holding exactly one item $i\in[n]$ with...

By Peter Bradshaw, Tomáš Masařík, Jana Novotná, and Ladislav Stacho
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1416-1435, June 2022.
Let $\Lambda(T)$ denote the set of leaves in a tree $T$. One natural problem is to...

By Moran Feldman, Ola Svensson, and Rico Zenklusen
SIAM Journal on Computing, Volume 51, Issue 3, Page 766-819, June 2022.
The secretary problem became one of the most prominent online selection problems due to its numerous applications...

By Arkadev Chattopadhyay and Nikhil S. Mande
SIAM Journal on Computing, Volume 51, Issue 3, Page 820-848, June 2022.
We exhibit a natural function $F_n$ on $n$ variables that can be computed by just a linear-size...

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 Tuan A. Do, Joshua Erde, and Mihyun Kang
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1394-1415, June 2022.
The genus of the binomial random graph $G(n,p)$ is well understood for a wide range of...

By Viresh Patel and Fabian Stroh
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1363-1393, June 2022.
We give a polynomial-time algorithm for detecting very long cycles in dense regular graphs. Specifically, we...

By Raphael M. Steiner
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1343-1362, June 2022.
A conjecture by Lichiardopol [SIAM J. Discrete Math., 28 (2014), pp. 1618--1627] states that for every...

By Michaela Coleman, Anton Dochtermann, Nathan Geist, and Suho Oh
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1291-1305, June 2022.
We say that a pure $d$-dimensional simplicial complex $\Delta$ on $n$ vertices is shelling completable if...

By Amin Coja-Oghlan, Philipp Loick, Balázs F. Mezei, and Gregory B. Sorkin
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1306-1342, June 2022.
The Ising antiferromagnet is an important statistical physics model with close connections to the Max Cut...

By Martin Böhm, Ruben Hoeksma, Nicole Megow, Lukas Nölke, and Bertrand Simon
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1249-1273, June 2022.
We consider the problem of computing a Steiner tree of minimum cost under a hop constraint...

By Pu Gao, Calum MacRury, and Paweł Prałat
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1274-1290, June 2022.
The semirandom graph process is a single player game in which the player is initially presented...

By Chih-Hung Liu
SIAM Journal on Computing, Volume 51, Issue 3, Page 723-765, June 2022.
We study the $k$ nearest neighbors problem in the plane for general, convex, pairwise disjoint sites of...

By Anna Adamaszek, Artur Czumaj, Matthias Englert, and Harald Räcke
SIAM Journal on Computing, Volume 51, Issue 3, Page 701-722, June 2022.
We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically,...

By Timothy F. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král, and Kristýna Pekárková
SIAM Journal on Computing, Volume 51, Issue 3, Page 664-700, June 2022.
A long line of research on fixed parameter tractability of integer programming culminated with showing that integer...

By James Oxley and Zach Walsh
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1231-1248, June 2022.
An integer matrix $A$ is $\Delta$-modular if the determinant of each $rank(A) \times rank(A)$ submatrix has...

By Dan Bergren, Eduard Eiben, Robert Ganian, and Iyad Kanj
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1200-1230, June 2022.
We study the problem of covering a set of segments on a line with the minimum...

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 Joshua Brakensiek, Sivakanth Gopi, and Venkatesan Guruswami
SIAM Journal on Computing, Volume 51, Issue 3, Page 577-626, June 2022.
We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight...

By Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti, Solon P. Pissis, and Giovanna Rosone
SIAM Journal on Computing, Volume 51, Issue 3, Page 549-576, June 2022.
An elastic-degenerate (ED) string is a sequence of $n$ sets of strings of total length $N$ which...

By Oliver Janzer, Abhishek Methuku, and Zoltán Lóránt Nagy
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1187-1199, June 2022.
The $r$-blowup of a graph $F$, denoted by $F[r]$, is the graph obtained by replacing the...

By Timothy M. Chan, Sariel Har-Peled, and Mitchell Jones
SIAM Journal on Computing, Volume 51, Issue 3, Page 627-663, June 2022.
We develop a general randomized technique for solving implicit linear programming problems, where the collection of constraints...

By Maria Elisa Fernandes and Claudio Alexandre Piedade
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1143-1155, June 2022.
We give a list of all possible degrees of faithful transitive permutation representations, corresponding to...

By Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1156-1186, June 2022.
We study the allocation of indivisible goods that form an undirected graph and quantify the loss...

By Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, and Mihalis Yannakakis
SIAM Journal on Computing, Volume 51, Issue 3, Page 492-548, June 2022.
We study the optimal lottery problem and the optimal mechanism design problem in the setting of a...

By Piotr Indyk and Tal Wagner
SIAM Journal on Computing, Volume 51, Issue 3, Page 467-491, June 2022.
We study the problem of representing all distances between $n$ points in ${\mathbb R}^d$, with arbitrarily small...

By Arturo Merino, Ondřej Mička, and Torsten Mütze
SIAM Journal on Computing, Volume 51, Issue 3, Page 379-423, June 2022.
The well-known middle levels conjecture asserts that for every integer $n\geq 1$, all binary strings of length...

By Paweł M. Idziak and Jacek Krzaczkowski
SIAM Journal on Computing, Volume 51, Issue 3, Page 337-378, June 2022.
The satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted either to...

By Péter Pál Pach and Richárd Palincza
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1135-1142, June 2022.
We show that sets avoiding six-term arithmetic progressions in $\mathbb{Z}_6^n$ have size at most $5.709^n$. It...

By Gilad Asharov, Wei-Kai Lin, and Elaine Shi
SIAM Journal on Computing, Volume 51, Issue 3, Page 424-466, June 2022.
We consider the classical problem of sorting an input array containing $n$ elements, where each element is...

By Huacheng Yu
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-174-STOC20-249, June 2022.
For positive integers $U$, $n$, and $\sigma$, given a set $S$ of $n$ (distinct) keys from key...

By Lijie Chen and Hanlin Ren
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-115-STOC20-173, June 2022.
In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018,...

By Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1102-1123, June 2022.
Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings...

By Ewan Davies and Freddie Illingworth
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1124-1134, June 2022.
In 1967, Erdös asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An...

By Tongseok Lim and Robert J. McCann
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1093-1101, June 2022.
In this paper, we explicitly estimate the number of points in a subset $A \subset...

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 Anup Rao and Amir Yehudayoff
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1071-1092, June 2022.
We prove anticoncentration bounds for the inner product of two independent random vectors and use these...

By Candida Bowtell and Joseph Hyde
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1038-1063, June 2022.
The study of asymptotic minimum degree thresholds that force matchings and tilings in hypergraphs is a...

By Ahmad Abdi, Gérard Cornuéjols, Bertrand Guenin, and Levent Tunçel
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1012-1037, June 2022.
A vector is dyadic if each of its entries is a dyadic rational number, i.e., an...

By Igor E. Shparlinski
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1064-1070, June 2022.
We obtain upper bounds on the cardinality of Hilbert cubes in finite fields, which avoid large...

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$, and...

By Thomas Kahle, Dinh Van Le, and Tim Römer
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 975-999, June 2022.
We relate finite generation of cones, monoids, and ideals in increasing chains (the local situation) to...

By Guorong Gao, An Chang, and Yuan Hou
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1000-1011, June 2022.
An $r$-uniform hypergraph is linear if every two edges intersect in at most one vertex. Let...

By Grigory Ivanov and Márton Naszódi
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 951-957, June 2022.
We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection...

By Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua Zahl
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 958-974, June 2022.
We show that the maximum number of pairwise nonoverlapping $k$-rich lenses (lenses formed by at least...

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 Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, and Ross J. Kang
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 939-950, June 2022.
We wish to bring attention to a natural but slightly hidden problem, posed by Erdös and...

By Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 911-921, June 2022.
In the literature on parameterized graph problems, there has been an increased effort in recent years...

By Karl Däubel
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 867-887, June 2022.
The ring loading problem emerged in the 1990s to model an important special case of telecommunication...

By Tomáš Masařík, Marcin Pilipczuk, Paweł Rzaͅżewski, and Manuel Sorge
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 922-938, June 2022.
The Directed Grid Theorem, stating that there is a function $f$ such that a directed graph...

By Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew Weinberg
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-75-STOC20-114, June 2022.
We provide the first separation in the approximation guarantee achievable by truthful and nontruthful algorithms for combinatorial...

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 M. Levent Doğan, Alperen A. Ergür, Jake D. Mundo, and Elias Tsigaridas
SIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 888-910, June 2022.
Motivated by applications in combinatorial geometry, we consider the following question: Let $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_m)$ be an...

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 Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn
SIAM Journal on Computing, Ahead of Print.
Consider an instance of Euclidean $k$-means or $k$-medians clustering. We show that the cost of the optimal solution is preserved up to...

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 Aris Filos-Ratsikas and Paul W. Goldberg
SIAM Journal on Computing, Ahead of Print.
We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, and Discrete Ham sandwich, showing that they are PPA-complete....

By Nir Bitansky, Dakshita Khurana, and Omer Paneth
SIAM Journal on Computing, Ahead of Print.
The round complexity of zero-knowledge protocols is a long-standing open question and is yet to be settled under standard assumptions. So far,...

By Siddharth Bhandari and Sayantan Chakraborty
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-54-STOC20-74, June 2022.
We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree...

By Aaron Bernstein, Maximilian Probst Gutenberg, and Christian Wulff-Nilsen
SIAM Journal on Computing, Ahead of Print.
Computing the strongly connected Components (SCCs) in a graph $G=(V,E)$ is known to take only $O(m + n)$ time using an algorithm...

By Mika Göös and Aviad Rubinstein
SIAM Journal on Computing, Ahead of Print.
We prove an $N^{2-o(1)}$ lower bound on the randomized communication complexity of finding an $\epsilon$-approximate Nash equilibrium (for constant $\epsilon>0$) in a...

By Aaron Bernstein and Danupon Nanongkai
SIAM Journal on Computing, Ahead of Print.
In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the...

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, Ahead of Print.
We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the...

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 Vera Traub, Jens Vygen, and Rico Zenklusen
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-24-STOC20-53, June 2022.
We present a black-box reduction from the path version of the traveling salesman problem (Path TSP) to...

By Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine Shi
SIAM Journal on Computing, Ahead of Print.
Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory;...

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 Alexander A. Sherstov and Pei Wu
SIAM Journal on Computing, Ahead of Print.
The threshold degree of a Boolean function $f\colon{{\{0,1\}}^n}\to{\{0,1\}}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign:...

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 Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes
SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-1-STOC20-23, June 2022.
For every constant $d \geq 3$ and $\epsilon > 0$, we give a deterministic $\operatorname{poly}(n)$-time algorithm that...

By Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao Low
SIAM Journal on Computing, Ahead of Print.
We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice...

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, Ahead of Print.
Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon...

By Urmila Mahadev
SIAM Journal on Computing, Ahead of Print.
We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to...

By Jatin Batra, Naveen Garg, and Amit Kumar
SIAM Journal on Computing, Ahead of Print.
In the weighted flow-time problem on a single machine, we are given a set of $n$ jobs, where each job has a...

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

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

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

Houston, TX, United States

Albuquerque, NM, United States

Albuquerque, NM, United States

Honolulu, HI, United States

Northampton, MA, United States

IL, United States

Smithfield, RI, United States

PA, United States

Albuquerque, NM, United States

Albuquerque, NM, United States

Clemson, SC, United States

Cambridge, MA, United States

Waco, TX, United States

Rahway, NJ, United States

Exeter, , United Kingdom

Clemson, SC, United States

Clemson, SC, United States

Bryn Mawr, PA, United States

Philadelphia, PA, United States

Fort Collins, CO, United States

Calgary, AB, Canada

Pennington, NJ, United States

Singapore

Singapore

Columbia, SC, United States

Baltimore, MD, United States

Albuquerque, NM, United States

Charlottesville, VA, United States

Klamath Falls, OR, United States

Rochester, NY, United States

Mohali, , India

Philippines

Baltimore, MD, United States

Beijing, , China

VA, United States

Clemson, SC, United States

Clemson, SC, United States

Hong Kong

Baltimore, MD, United States

Blacksburg - Main Campus, VA, United States

Baltimore, MD, United States

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

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

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.

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.

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.

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.