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 Minglong Qin and Penghui Yao SIAM Journal on Computing, Volume 50, Issue 6, Page 1800-1891, January 2021. This paper considers a special class of nonlocal games $(G,\psi)$, where $G$ is a two-player one-round game,...

By Miriam Backens SIAM Journal on Computing, Volume 50, Issue 6, Page 1739-1799, January 2021. Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined...

By Nathan Benedetto Proença, Marcel K. de Carli Silva, and Gabriel Coutinho SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2880-2907, January 2021. The notion of duality is a key element in understanding the interplay between the stability and...

By Bin Han, Jianxi Mao, and Jiang Zeng SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2858-2879, January 2021. We consider a sequence of four variable polynomials by refining Stieltjes's continued fraction for...

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 Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang SIAM Journal on Computing, Volume 50, Issue 6, Page 1701-1738, January 2021. We give the first efficient algorithm to approximately count the number of solutions in the random $k$-SAT...

By Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Yoshiharu Kohayakawa, and Tássio Naia SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2844-2857, January 2021. If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec...

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 François Pirot and Jean-Sébastien Sereni SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2815-2843, January 2021. We introduce a new method for computing bounds on the independence number and fractional chromatic number...

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 Minglong Qin and Penghui Yao SIAM Journal on Computing, Volume 50, Issue 6, Page 1800-1891, January 2021. This paper considers a special class of nonlocal games $(G,\psi)$, where $G$ is a two-player one-round game,...

By Miriam Backens SIAM Journal on Computing, Volume 50, Issue 6, Page 1739-1799, January 2021. Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined...

By Nathan Benedetto Proença, Marcel K. de Carli Silva, and Gabriel Coutinho SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2880-2907, January 2021. The notion of duality is a key element in understanding the interplay between the stability and...

By Bin Han, Jianxi Mao, and Jiang Zeng SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2858-2879, January 2021. We consider a sequence of four variable polynomials by refining Stieltjes's continued fraction for...

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 Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan Yang SIAM Journal on Computing, Volume 50, Issue 6, Page 1701-1738, January 2021. We give the first efficient algorithm to approximately count the number of solutions in the random $k$-SAT...

By Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Yoshiharu Kohayakawa, and Tássio Naia SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2844-2857, January 2021. If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec...

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 François Pirot and Jean-Sébastien Sereni SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2815-2843, January 2021. We introduce a new method for computing bounds on the independence number and fractional chromatic number...

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 Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav Živný SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2749-2814, January 2021. We study the problem of computing the parity of the number of homomorphisms from an input...

By Joshua Brakensiek and Venkatesan Guruswami SIAM Journal on Computing, Volume 50, Issue 6, Page 1663-1700, January 2021. A classic result due to Schaefer [Proceedings of STOC 78, ACM, 1978, pp. 216--226] classifies all constraint...

By Dennis Clemens, Fabian Hamann, Yannick Mogge, and Olaf Parczyk SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2723-2748, January 2021. Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of...

By Logan Crew and Sophie Spirkl SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2647-2661, January 2021. In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions...

By Tzvi Alon and Nir Halman SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2679-2722, January 2021. In this paper we go one step further in the automatic generation of FPTASes for multistage...

By Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2662-2678, January 2021. In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing...

By Jisu Jeong, Eun Jung Kim, and Sang-il Oum SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2544-2617, January 2021. Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field ${\mathbb F}$, we...

By Clément Dallard, Martin Milanič, and Kenny Štorgel SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2618-2646, January 2021. Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition...

By Hong-Jian Lai and Lucian Mazza SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2535-2543, January 2021. Abelian group colorings were first introduced by Jaeger et al. in [J. Combin. Theory Ser. B,...

By Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska Williams SIAM Journal on Computing, Volume 50, Issue 5, Page 1627-1662, January 2021. We consider the pattern detection problem in graphs: given a constant size pattern graph $H$ and a...

By Artur Czumaj, Peter Davies, and Merav Parter SIAM Journal on Computing, Volume 50, Issue 5, Page 1603-1626, January 2021. We settle the complexity of the $(\Delta+1)$-coloring and $(\Delta+1)$-list coloring problems in the \sf CONGESTED CLIQUE model...

By René Sitters SIAM Journal on Computing, Volume 50, Issue 5, Page 1580-1602, January 2021. We give a polynomial time approximation scheme for the weighted traveling repairman problem (TRP) in the Euclidean...

By Momoko Hayamizu SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2490-2516, January 2021. Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis....

By Nathan Bowler, Joshua Erde, Florian Lehner, and Max Pitz SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2459-2489, January 2021. It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded...

By Dani Kotlar, Elad Roda, and Ran Ziv SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2517-2519, January 2021. We show that given two bases $A$ and $B$ of a matroid $\mathcal M$ and any...

By Xiaofeng Gu, Wei Meng, Martin Rolek, Yue Wang, and Gexin Yu SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2520-2534, January 2021. The 2-dimensional global rigidity has been shown to be equivalent to 3-connectedness and redundant rigidity by...

By Bart M. P. Jansen, Marcin L. Pilipczuk, and Erik Jan van Leeuwen SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2387-2429, January 2021. We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted...

By Oliver Cooley, Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolás Sanhueza-Matamala, and Julian Zalla SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2430-2458, January 2021. Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight...

By Vera Traub, Jens Vygen, and Rico Zenklusen SIAM Journal on Computing, Ahead of Print. We present a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP)....

By Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzaͅżewski, and Sophie Spirkl SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2357-2386, January 2021. We study the Max Partial $H$-Coloring problem: given a graph $G$, find the largest induced subgraph...

By S. Thomas McCormick, Britta Peis, Robert Scheidweiler, and Frank Vallentin SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2345-2356, January 2021. In this note we give a polynomial time algorithm for solving the closest vector problem...

By Bernard Lidický and Florian Pfender SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2328-2344, January 2021. Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra...

By Jun Gao, Qingyi Huo, and Jie Ma SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2317-2327, January 2021. Resolving a conjecture of Bollobás and Erdös, Gyárfás proved that every graph $G$ of chromatic number...

By Vipul Goyal, Silas Richelson, Alon Rosen, and Margarita Vald SIAM Journal on Computing, Volume 50, Issue 5, Page 1537-1579, January 2021. In their seminal work on nonmalleable cryptography, Dolev, Dwork, and Naor showed how to construct a nonmalleable...

By Oliver Weller-Davies, Mike Steel, and Jotun Hein SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2304-2316, January 2021. Polymer models are a widely used tool to study the prebiotic formation of metabolism at the...

By Ron Aharoni, Joseph Briggs, Ron Holzman, and Zilin Jiang SIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2293-2303, January 2021. We prove that every family of (not necessarily distinct) odd cycles $O_1, \dots, O_{2\lceil n/2 \rceil-1}$...

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 Felix Hommelsheim, Moritz Muehlenthaler, and Oliver Schaudt SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2265-2292, January 2021. Suppose we are given a bipartite graph that admits a perfect matching and an adversary may...

By Weiting Cao, Douglas B. West, and Yan Yang SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2234-2248, January 2021. A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in...

By David Conlon and Mykhaylo Tyomkyn SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2249-2264, January 2021. For a fixed graph $H$, what is the smallest number of colors $C$ such that there...

By Edita Máčajová and Martin Škoviera SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2223-2233, January 2021. The well-known shortest cycle cover conjecture suggests that every bridgeless graph $G$ can have its edges...

By Luiz Moreira SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2210-2222, January 2021. We say that a graph $G$ is Ramsey for $H_1$ versus $H_2$ and write $G \to...

By Gilad Asharov, Moni Naor, Gil Segev, and Ido Shahaf SIAM Journal on Computing, Volume 50, Issue 5, Page 1501-1536, January 2021. Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting...

By Patrick Bennett, Ryan Cushman, and Andrzej Dudek SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2145-2169, January 2021. A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $\tau(G)$ is at most...

By Kristóf Bérczi, Tamás Schwarcz, and Yutaro Yamaguchi SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2192-2209, January 2021. In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\mathcal{I}}_1)$ and $M_2=(S,{\mathcal{I}}_2)$ on...

By Shang-En Huang and Seth Pettie SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2129-2144, January 2021. We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for...

By Sam Spiro and Jacques Verstraëte SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2170-2191, January 2021. For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of...

By Guozhen Rong, Wenjun Li, Jianxin Wang, and Yongjie Yang SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2115-2128, January 2021. In 1990, Hendry conjectured that all Hamiltonian chordal graphs are cycle extendable. After a series of...

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 Linus Setiabrata SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2093-2114, January 2021. For every directed acyclic graph $G$, we characterize the faces of the root polytope $\tilde Q_G...

By Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2070-2092, January 2021. The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$...

By Eric N. Stucky SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2049-2069, January 2021. We discuss two surprising properties of a family of polynomials that generalize the Mahonian $q$-Catalan polynomials...

By Hans L. Bodlaender, Sudeshna Kolay, and Astrid Pieterse SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2003-2038, January 2021. Given a graph $G$, a $q$-open neighborhood conflict-free coloring or $q$-ONCF-coloring is a vertex coloring $c\colon...

By Thomas Magnard, Michael Skotnica, and Martin Tancer SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1978-2002, January 2021. We say that a pure simplicial complex ${\mathbf K}$ of dimension $d$ satisfies the removal-collapsibility condition...

By Qing Cui and On-Hei Solomon Lo SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2039-2048, January 2021. For any positive integer $k$, define $f(k)$ (respectively, $f_3(k)$) to be the minimal integer $\ge k$...

By Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. Venkitesh SIAM Journal on Computing, Volume 50, Issue 4, Page 1461-1499, January 2021. In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform ${\mathrm{AC}}^0[\oplus]$. In particular, we show...

By Radoslav Fulek and Balázs Keszegh SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1964-1977, January 2021. A 0-1 matrix $M$ is saturating for a 0-1 matrix $P$ if $M$ does not contain...

By Papa A. Sissokho SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1952-1963, January 2021. Let $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ be fixed positive integers, and let ${\mathcal S}$ denote the set of...

By Johannes Bausch and Felix Leditzky SIAM Journal on Computing, Volume 50, Issue 4, Page 1410-1460, January 2021. The error threshold of a one-parameter family of quantum channels is defined as the largest noise level...

By Manuel Bodirsky, Florent Madelaine, and Antoine Mottet SIAM Journal on Computing, Volume 50, Issue 4, Page 1359-1409, January 2021. The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries...

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 Lucas de Oliveira Contiero, Carlos Hoppen, Hanno Lefmann, and Knut Odermann SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1927-1951, January 2021. The Fano plane is the unique linear 3-uniform hypergraph on seven vertices and seven hyperedges. It...

By Michael Anastos, Alan Frieze, and Pu Gao SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1854-1880, January 2021. We study the Hamiltonicity of the following model of a random graph. Suppose that we partition...

By Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1792-1853, January 2021. As is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3...

By Benjamin Bergougnoux and Mamadou Moustapha Kanté SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1881-1926, January 2021. In this paper, we design a framework to obtain efficient algorithms for several problems with a...

By Moïse Blanchard, Jesús A. De Loera, and Quentin Louveaux SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1746-1768, January 2021. Motivated by the problem of bounding the number of iterations of the simplex algorithm, we investigate...

By Daniel W. Cranston and Matthew P. Yancey SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1769-1791, January 2021. For each integer $k\ge 2$, we determine a sharp bound on ${mad}(G)$ such that $V(G)$ can...

By Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini Sgouritsa SIAM Journal on Computing, Volume 50, Issue 4, Page 1336-1358, January 2021. The fair division of indivisible goods is a very well-studied problem. The goal of this problem is...

By Wanshun Yang, Yiqiao Wang, Weifan Wang, and Ko-Wei Lih SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1729-1745, January 2021. A 1-planar graph is a graph that can be drawn in the Euclidean plane such that...

By Yi Li, Ruosong Wang, and David P. Woodruff SIAM Journal on Computing, Volume 50, Issue 4, Page 1287-1335, January 2021. In the subspace sketch problem one is given an $n \times d$ matrix $A$ with $O(\log(nd))$ bit...

By Carol T. Zamfirescu SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1706-1728, January 2021. Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both...

By Imre Leader, Žarko Ranđelović, and Eero Räty SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1678-1687, January 2021. In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by...

By Rohit Gurjar and Nisheeth K. Vishnoi SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1688-1705, January 2021. We show that for any regular matroid on m elements and $\alpha \geq 1$, the number...

By Marcin Kozik SIAM Journal on Computing, Volume 50, Issue 4, Page 1263-1286, January 2021. The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as...

By James A. Long, Kevin G. Milans, and Andrea Munaro SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1673-1677, January 2021. We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of...

By Shachar Lovett SIAM Journal on Computing, Volume 50, Issue 4, Page 1248-1262, January 2021. A $k \times n$ matrix over a field is called an MDS (maximum distance separable) matrix if...

By Mokshay Madiman, Liyao Wang, and Jae Oh Woo SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1628-1649, January 2021. Lower bounds for the Rényi entropies of sums of independent random variables taking values in cyclic...

By Jang Soo Kim and Meesue Yoo SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1650-1672, January 2021. In the literature there are several determinant formulas for Schur functions: the Jacobi--Trudi formula, the dual...

By Travis Dillon and Pablo Soberón SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1615-1627, January 2021. A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a...

By Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. Tóth SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1592-1614, January 2021. Let $P=(p_1, p_2, \dots, p_n)$ be a polygonal chain in $\mathbb{R}^d$. The stretch factor of $P$...

By Siu-Wing Cheng and Man-Kit Lau SIAM Journal on Computing, Volume 50, Issue 4, Page 1200-1247, January 2021. We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let...

By Oleg R. Musin SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1578-1591, January 2021. In the present paper, we consider the majorization theorem (also known as Karamata's inequality) and the...

By Elad Aigner-Horev and Dan Hefetz SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1569-1577, January 2021. Given an $n$-vertex graph $H$ with minimum degree at least $d n$ for some fixed $d...

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 Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca Trevisan SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1557-1568, January 2021. For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The...

By Jozsef Balogh, Nathan Lemons, and Cory Palmer SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1525-1535, January 2021. Let $\mathcal{H}$ be an $r$-uniform hypergraph. The minimum positive co-degree of $\mathcal{H}$, denoted by $\delta_{r-1}^+(\mathcal{H})$, is...

By Martin Vodička SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1536-1547, January 2021. The Kimura 3-parameter model is one of the most fundamental phylogenetic models in algebraic statistics. We...

By Tao Zhang and Gennian Ge SIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1548-1556, January 2021. For an $r$-graph $G$, the minimum $(r-1)$-degree $\delta(G)$ is the largest integer $t$ such that every...

By Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole Wein SIAM Journal on Computing, Volume 50, Issue 4, Page 1155-1199, January 2021. Among the most important graph parameters is the diameter, the largest distance between any two vertices. There...

By Jérémie Dusart, Derek G. Corneil, and Michel Habib SIAM Journal on Computing, Volume 50, Issue 3, Page 1148-1153, January 2021. This corrigendum corrects errors found by Jérémie Dusart in the proof of correctness of the algorithms in...

By Alexandr Andoni, Keren Censor-Hillel, Jing Chen, and Debmalya Panigrahi SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-i-STOC16-iii, January 2021. This issue of SICOMP contains 14 specially selected papers from the 48th Annual ACM Symposium on Theory...

By Martin Dyer, Mark Jerrum, Haiko Müller, and Kristina Vušković SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1503-1524, January 2021. Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any...

By John Engbers, Aysel Erey, Jacob Fox, and Xiaoyu He SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1478-1502, January 2021. Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture,...

By Safwat Nassar and Raphael Yuster SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1460-1477, January 2021. What must one do in order to make acyclic a given oriented graph? Here we look...

By Keren Censor-Hillel and Michal Dory SIAM Journal on Computing, Volume 50, Issue 3, Page 1103-1147, January 2021. We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the...

By Tsz Chiu Kwok, Lap Chi Lau, and Akshay Ramachandran SIAM Journal on Computing, Volume 50, Issue 3, Page 1034-1102, January 2021. We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The...

By Yoshiharu Kohayakawa, Walner Mendonça, Guilherme Oliveira Mota, and Bjarne Schülke SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1447-1459, January 2021. We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices...

By Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, and Martin Strehler SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1418-1446, January 2021. Graph searches and the corresponding search trees can exhibit important structural properties and are used in...

By Fedor V. Fomin and Petr A. Golovach SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1298-1336, January 2021. A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic,...

By Sándor P. Fekete, Linda Kleist, and Dominik Krupke SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1337-1355, January 2021. We provide a comprehensive study of a natural graph optimization problem that arises from transition costs...

By Ben Clark, Kevin Grace, James Oxley, and Stefan H. M. van Zwam SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1356-1380, January 2021. Subject to announced results by Geelen, Gerards, and Whittle [Towards a structure theory for matrices and...

By Wenjian Liu and Ning Ning SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1381-1417, January 2021. In this paper, we analyze the tree reconstruction problem, which is to determine whether symbols at...

By David Eppstein and Vijay V. Vazirani SIAM Journal on Computing, Volume 50, Issue 3, Page 1014-1033, January 2021. In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in $K_{3,3}$-minor-free graphs...

By Srinivasan Arunachalam, Alex Bredariol Grilo, and Aarthi Sundaram SIAM Journal on Computing, Volume 50, Issue 3, Page 972-1013, January 2021. In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and...

By Edita Máčajová and Martin Škoviera SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1287-1297, January 2021. The perfect matching index of a cubic graph $G$, denoted by $\pi(G)$, is the smallest...

By Duško Jojić, Gaiane Panina, and Rade Živaljević SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1268-1286, January 2021. We prove several versions of Alon's necklace-splitting theorem, subject to additional constraints, as illustrated by the...

By Stefan Kiefer and Corto N. Mascle SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1252-1267, January 2021. Let $n$ be a natural number, and let $\mathcal{M}$ be a set of $n \times n$-matrices...

By Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique Stagni SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1238-1251, January 2021. Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given...

By Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming Sun SIAM Journal on Computing, Volume 50, Issue 3, Page 924-971, January 2021. In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of...

By Louis Esperet, Cyril Gavoille, and Carla Groenland SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1224-1237, January 2021. A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$...

By Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin Leuner SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1201-1223, January 2021. In this paper we describe a parallel algorithm for generating all nonisomorphic rank 3 simple matroids...

By Alan M. Frieze SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1182-1200, January 2021. We consider the following question. We have a dense regular graph $G$ with degree $\alpha n$,...

By Aleksandrs Belovs and Eric Blais SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-406-STOC16-433, January 2021. We show that every algorithm for testing $n$-variate Boolean functions for monotonicity must have query complexity $\tilde{\Omega}(n^{1/4})$....

By Debsoumya Chakraborti, Da Qi Chen, and Mihir Hasabnis SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1165-1181, January 2021. This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite...

By Zdeněk Dvořák, Rose McCarty, and Sergey Norin SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1149-1164, January 2021. We give a natural sufficient condition for an intersection graph of compact convex sets in $\mathbb{R}^d$...

By Maria Axenovich, Jean-Sébastien Sereni, Richard Snyder, and Lea Weber SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1136-1148, January 2021. We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole...

By Amin Coja-Oghlan and Max Hahn-Klimroth SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1096-1135, January 2021. Guided by the theory of graph limits, we investigate a variant of the cut metric for...

By Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat Lee SIAM Journal on Computing, Volume 50, Issue 3, Page 909-923, January 2021. We consider metrical task systems on tree metrics and present an $O(\mathrm{depth} \times \log n)$-competitive randomized algorithm...

By Dongchun Han and Hanbin Zhang SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1077-1095, January 2021. In this paper, we present a reciprocity on finite abelian groups involving zero-sum sequences. Let $G$...

By Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra SIAM Journal on Computing, Ahead of Print. We show that for constraint satisfaction problems (CSPs), weakly exponential size linear programming relaxations are as powerful as the explicit linear program...

By Alan Arroyo, R. Bruce Richter, and Matthew Sunohara SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1050-1076, January 2021. Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of...

By Hongliang Lu, Xingxing Yu, and Xiaofan Yuan SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1022-1049, January 2021. We prove that, for any integers $k,l$ with $k\ge 3$ and $k/2

By Xiaonan Liu and Xingxing Yu SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1005-1021, January 2021. Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured...

By Rajko Nenadov and Miloš Trujić SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 988-1004, January 2021. A seminal result by Komlós, Sarközy, and Szemerédi states that if a graph $G$ with $n$...

By Andrea Freschi, Joseph Hyde, Joanna Lada, and Andrew Treglown SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 970-975, January 2021. Balogh, Csaba, Jing, and Pluhár [Electron. J. Combin., 27 (2020)] recently determined the minimum degree threshold...

By Igor E. Shparlinski and Qiang Wang SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 976-987, January 2021. We obtain new bounds of exponential sums modulo a prime $p$ with sparse polynomials ...

By Xiaofeng Gu SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 948-952, January 2021. The toughness $t(G)$ of a connected graph $G$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$, in which the minimum...

By Guillaume Ducoffe SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 953-969, January 2021. Given an $n$-vertex $m$-edge graph $G$ with nonnegative edge-weights, a shortest cycle is one minimizing the...

By Wojciech Czerwiński, Wojciech Nadara, and Marcin Pilipczuk SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 934-947, January 2021. Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in...

By Amit Sahai and Brent Waters SIAM Journal on Computing, Volume 50, Issue 3, Page 857-908, January 2021. We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems....

By Bill Jackson, Anthony Nixon, and Shin-ichi Tanigawa SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 928-933, January 2021. We consider the problem of characterizing the generic rigidity of bar-joint frameworks in $\mathbb{R}^d$ in which...

By Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph Lenzen SIAM Journal on Computing, Volume 50, Issue 3, Page 815-856, January 2021. We present a method for solving the transshipment problem---also known as uncapacitated minimum cost flow---up to a...

By Gábor Damásdi, Stefan Felsner, António Gira͂o, Balázs Keszegh, David Lewis, Dániel T. Nagy, and Torsten Ueckerdt SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 915-927, January 2021. We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite...

By Henning Bruhn, Felix Joos, and Oliver Schaudt SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 893-914, January 2021. In the 1960s, Erdös and Pósa proved that there is a packing-covering duality for cycles in...

By Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dušan Knop, and Peter Zeman SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 840-892, January 2021. We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known...

By Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-377-STOC16-405, January 2021. Adaptivity is an important feature of data analysis---the choice of questions to ask about a dataset often...

By Ivan Aidun, Frances Dean, Ralph Morrison, Teresa Yu, and Julie Yuan SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 814-839, January 2021. We associate to any graph a sequence of integers called the gonality sequence of the graph,...

By Tom Gur and Oded Lachish SIAM Journal on Computing, Volume 50, Issue 2, Page 788-813, January 2021. A locally decodable code (LDC) $C \colon \{0,1\}^k \to \{0,1\}^n$ is an error correcting code wherein individual...

By Pankaj K. Agarwal, Boris Aronov , Esther Ezra , and Joshua Zahl SIAM Journal on Computing, Volume 50, Issue 2, Page 760-787, January 2021. In 2015, Guth proved that if $\EuScript{S}$ is a collection of $n$ $g$-dimensional semialgebraic sets in ${\mathbb{R}}^d$...

By Hoon Oh, Ariel D. Procaccia, and Warut Suksompong SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 788-813, January 2021. We investigate the query complexity of the fair allocation of indivisible goods. For two agents with...

By Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, and Jens Vygen SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 752-769, January 2021. We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if...

By Magnús M. Halldórsson and Tigran Tonoyan SIAM Journal on Computing, Volume 50, Issue 2, Page 718-759, January 2021. An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can...

By Stasys Jukna SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 770-787, January 2021. The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s...

By Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun Zhang SIAM Journal on Computing, Volume 50, Issue 2, Page 674-717, January 2021. In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets...

By Martín D. Safe SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 707-751, January 2021. In 1969, Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the...

By Greg Bodwin SIAM Journal on Computing, Volume 50, Issue 2, Page 662-673, January 2021. Given $p$ node pairs in an $n$-node graph, a distance preserver is a sparse subgraph that agrees...

By Haitao Wang and Jingru Zhang SIAM Journal on Computing, Volume 50, Issue 2, Page 602-635, January 2021. We consider a classical $k$-center problem in trees. Let $T$ be a tree of $n$ vertices such...

By Pasin Manurangsi and Warut Suksompong SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 668-706, January 2021. We study a resource allocation setting where $m$ discrete items are to be divided among $n$...

By Rose McCarty SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 661-667, January 2021. We prove that every bipartite graph of sufficiently large average degree has either a $K_{t,t}$-subgraph or...

By Rohit Gurjar, Thomas Thierauf, and Nisheeth K. Vishnoi SIAM Journal on Computing, Volume 50, Issue 2, Page 636-661, January 2021. We present a geometric approach toward derandomizing the isolation lemma of Mulmuley, Vazirani, and Vazirani. We...

By Oleg Karpenkov and Christian Mueller SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 637-660, January 2021. In this paper we study a classical Maxwell question on the existence of self-stresses for frameworks,...

By O-joung Kwon and Jean-Florent Raymond SIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 597-636, January 2021. A class $\mathcal{F}$ of graphs has the induced Erdös--Pósa property if there exists a function $f$...

By Harold N. Gabow and Piotr Sankowski SIAM Journal on Computing, Volume 50, Issue 2, Page 555-601, January 2021. For an undirected graph or multigraph $G=(V,E)$ and a function $f:V\to \mathbb{Z_+}$, an $f$-factor is a...

By Karolina Okrasa and Paweł Rzaͅżewski SIAM Journal on Computing, Volume 50, Issue 2, Page 487-508, January 2021. For a fixed graph $H$, by Hom($H$) we denote the computational problem which asks whether a given...

By Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren Weimann SIAM Journal on Computing, Volume 50, Issue 2, Page 509-554, January 2021. We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$...

By Harold N. Gabow and Piotr Sankowski SIAM Journal on Computing, Volume 50, Issue 2, Page 440-486, January 2021. Let $G=(V,E)$ be a weighted graph or multigraph, with $f$ or $b$ a function assigning a nonnegative...

By Rajesh Jayaram and David Woodruff SIAM Journal on Computing, Volume 50, Issue 2, Page 382-439, January 2021. In this paper, we resolve the one-pass space complexity of perfect $L_p$ sampling for $p \in (0,2)$...

By Pavel Dvořák, Andreas E. Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, and Pavel Veselý SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 546-574, January 2021. We study the Steiner Tree problem, in which a set of terminal vertices needs to be...

By Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak, and Magnus Wahlström SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 575-596, January 2021. Golovach, Paulusma, and Song [Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized...

By Weiming Feng, Nisheeth K. Vishnoi, and Yitong Yin SIAM Journal on Computing, Volume 50, Issue 2, Page 350-381, January 2021. In this paper, we study the problem of sampling from a graphical model when the model...

By M. McDevitt and N. Ruškuc SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 495-520, January 2021. Algorithmic decidability is established for two order-theoretic properties of downward closed subsets defined by finitely many...

By Marcin Briański, Piotr Micek, Michał Pilipczuk, and Michał T. Seweryn SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 447-464, January 2021. We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$,...

By Michael Tait and Robert Won SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 521-531, January 2021. An $m$-general set in $AG(n,q)$ is a set of points such that any subset of size...

By Qizhong Lin and Xing Peng SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 532-545, January 2021. Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all ...

By Eyal Kushilevitz, Rafail Ostrovsky, Emmanuel Prouff, Adi Rosén, Adrian Thillard, and Damien Vergnaud SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 465-484, January 2021. We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of...

By Ngo Dac Tan SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 485-494, January 2021. M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687--694]...

By Henning Bruhn-Fujimoto and Matthias Heinlein SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 392-430, January 2021. We prove that every graph $G$ contains either $k$ edge-disjoint $K_4$-subdivisions or a set $X$ of...

By Runrun Liu, Martin Rolek, D. Christopher Stephens, Dong Ye, and Gexin Yu SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 431-446, January 2021. For a given graph $H$, a graph $G$ is H-linked if, for every injection $\varphi: V(H)...

By Miaomiao Han, Jiaao Li, Rong Luo, Yongtang Shi, and Cun-Quan Zhang SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 376-391, January 2021. This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular...

By Matteo Gallet, Georg Grasegger, Jan Legerský, and Josef Schicho SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 325-361, January 2021. We interpret realizations of a graph on the sphere up to rotations as elements of a...

By Pavol Hell, César Hernández-Cruz, Jing Huang, and Jephian C.-H. Lin SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 362-375, January 2021. We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella...

By Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-Shma SIAM Journal on Computing, Volume 50, Issue 2, Page 301-349, January 2021. We strengthen the notion of double samplers, first introduced by Dinur and Kaufman [``High dimensional expanders imply...

By William M. Hoza and Chris Umans SIAM Journal on Computing, Ahead of Print. Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by...

By Quentin Dubroff, Jacob Fox, and Max Wenqiang Xu SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 322-324, January 2021. We present two short proofs giving the best known asymptotic lower bound for the maximum element...

By A. Nicholas Day and Amites Sarkar SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 294-306, January 2021. We disprove a conjecture of Nagy on the maximum number of copies $N$($G$, $H$) of a...

By Ilya Shkredov and Jozsef Solymosi SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 307-321, January 2021. In this paper we show examples for applications of the Bombieri--Lang conjecture in additive combinatorics, giving...

By Moran Feldman, Ola Svensson, and Rico Zenklusen SIAM Journal on Computing, Volume 50, Issue 2, Page 255-300, January 2021. We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution...

By Nina Kamcev, Anita Liebenau, David R. Wood, and Liana Yepremyan SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 281-293, January 2021. A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges...

By P. Dütting, T. Roughgarden, and I. Talgam-Cohen SIAM Journal on Computing, Volume 50, Issue 1, Page 211-254, January 2021. We initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing...

By Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes SIAM Journal on Computing, Ahead of Print. For every constant $d \geq 3$ and $\epsilon > 0$, we give a deterministic $\operatorname{poly}(n)$-time algorithm that outputs a $d$-regular graph on...

By Oliver Cooley, Nemanja Draganić, Mihyun Kang, and Benny Sudakov SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 267-280, January 2021. Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$...

By Louis DeBiasio, Allan Lo, Theodore Molla, and Andrew Treglown SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 250-266, January 2021. Let $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph...

By Dustin G. Mixon and Hans Parshall SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 234-249, January 2021. For $d\in\{5,6\}$, we classify arrangements of $d + 2$ points in ${RP}^{d-1}$ for which the minimum...

By Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi SIAM Journal on Computing, Volume 50, Issue 1, Page 171-210, January 2021. Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1\}^{n}\to \{0,1\}$ to the communication...

By Alexander Garver, Stefan Grosser, Jacob P. Matherne, and Alejandro Morales SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 205-233, January 2021. We introduce a class of posets, which includes both ribbon posets (skew shapes) and $d$-complete posets,...

By Oliver Roche-Newton SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 194-204, January 2021. Let $A \subset \mathbb R$ and $G \subset A \times A$. We prove that for any...

By Satoshi Noguchi, Xiao-Nan Lu, Masakazu Jimbo, and Ying Miao SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 179-193, January 2021. BCH codes are among the best practical cyclic codes widely used in consumer electronics, communication systems,...

By Steffen Borgwardt and Charles Viss SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 152-178, January 2021. Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations,...

By Hernán González-Aguilar, David Orden, Pablo Pérez-Lantero, David Rappaport, Carlos Seara, Javier Tejel, and Jorge Urrutia SIAM Journal on Computing, Volume 50, Issue 1, Page 145-170, January 2021. Let $P$łabelpage1 be a set of $n$ points in the plane. We consider a variation of the...

By Archontia Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin Wrochna SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 105-151, January 2021. Suppose ${\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion:...

By Nir Bitansky, Akshay Degwekar, and Vinod Vaikuntanathan SIAM Journal on Computing, Volume 50, Issue 1, Page 98-144, January 2021. Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of...

By Meysam Alishahi and Frédéric Meunier SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 91-104, January 2021. Haviv [European J. Combin., 81 (2019), pp. 84--97] has recently proved that some topological lower...

By Benny Applebaum, Zvika Brakerski, and Rotem Tsabary SIAM Journal on Computing, Volume 50, Issue 1, Page 68-97, January 2021. We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and...

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 Satoru Iwata and Yusuke Kobayashi SIAM Journal on Computing, Ahead of Print. The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that...

By Laurent Feuilloley and Michel Habib SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 55-90, January 2021. This paper deals with the characterization and the recognition of graph classes. A popular way to...

By Hélène Barcelo, Curtis Greene, Abdul Salam Jarrah, and Volkmar Welker SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 35-54, January 2021. We prove that if $G$ is a graph without 3-cycles and 4-cycles, then the discrete cubical...

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 Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de Mesmay SIAM Journal on Computing, Volume 50, Issue 1, Page 1-31, January 2021. For an undirected edge-weighted graph $G$ and a set $R$ of pairs of vertices called pairs of...

By Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini Vasudevan SIAM Journal on Computing, Volume 50, Issue 1, Page 32-67, January 2021. In the conditional disclosure of secrets (CDS) problem [Gertner et al., J. Comput. System Sci., 60 (2000),...

By Hiroki Oshima SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 1-22, January 2021. Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization...

By Qizhong Lin and Xiudi Liu SIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 23-34, January 2021. The notion of goodness for Ramsey numbers was introduced by Burr and Erdös in 1983. For...

By Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat SIAM Journal on Computing, Ahead of Print. In the classical node-disjoint paths (\sf NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection ${\mathcal M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$...

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

By Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan SIAM Journal on Computing, Ahead of Print. It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with $n$ nodes and $m$ distinct...

By Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma SIAM Journal on Computing, Ahead of Print. The breakthrough result of Chattopadhyay and Zuckerman [Explicit two-source extractors and resilient functions, in Proceedings of the 48th Annual ACM SIGACT Symposium...

By Jin-Yi Cai and Zhiguo Fu SIAM Journal on Computing, Ahead of Print. We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (#CSP) over Boolean variables into exactly three classes: (1)...

By Danny Nguyen and Igor Pak SIAM Journal on Computing, Ahead of Print. We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by “short” we mean sentences with a bounded number...

By Elaine Levey and Thomas Rothvo SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-201-STOC16-217, January 2021. In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and...

By Yang Cai, Nikhil R. Devanur, and S. Matthew Weinberg SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-160-STOC16-200, January 2021. We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions...

By Stephen Fenner, Rohit Gurjar, and Thomas Thierauf SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-218-STOC16-235, January 2021. We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits...

By Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-255-STOC16-340, January 2021. The celebrated ${\sf IP}={\sf PSPACE}$ theorem [Lund, Fortnow, Karloff, and Nisan, J. ACM, 39 (1992), pp. 859--868;...

By Anat Ganor, Gillat Kol, and Ran Raz SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-236-STOC16-254, January 2021. We show an exponential gap between communication complexity and external information complexity by analyzing a communication task...

By Nikhil Bansal, Aravind Srinivasan, and Ola Svensson SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-138-STOC16-159, January 2021. We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum...

By Sepehr Assadi, Sanjeev Khanna, and Yang Li SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-341-STOC16-376, January 2021. We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For...

By Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-98-STOC16-137, January 2021. We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted...

By Leqi Zhu SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-18-STOC16-29, January 2021. In the consensus problem, there are $n$ processes that each has a private input value. Each nonfaulty...

By Shaddin Dughmi and Haifeng Xu SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-68-STOC16-97, January 2021. Persuasion, defined as the act of exploiting an informational advantage in order to influence the decisions of...

By Shahar Dobzinski SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-1-STOC16-17, January 2021. We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial...

By Gil Cohen SIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-30-STOC16-67, January 2021. In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $(2+o(1))\log{n}$-Ramsey graphs on...

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.

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.

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.

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.

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