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.

Upcoming Conferences

ACM-SIAM Symposium on Discrete Algorithms (SODA19)

January 6 - 9, 2019 San Diego, California, USA More Information

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.

By Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Dan McQuillan, Bojan Mohar, Petra Mutzel, Pedro Ramos, R. Bruce Richter, and Birgit Vogtenhuber SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2482-2492, January 2018. The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of...

By Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2512-2565, January 2018. Seymour's decomposition theorem for regular matroids is a fundamental result with a number of...

By Ben Krause SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2493-2511, January 2018. We extend the main result of Harrow, Kolla, and Schulman---the existence of dimension-free $L^2$-bounds for the...

By Man-Kwun Chiu and Matias Korman SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2566-2590, January 2018. We consider the problem of digitalizing Euclidean line segments from $\mathbb{R}^d$ to $\mathbb{Z}^d$. Christ, Pálvölgyi, and...

By Anthony Nixon, Bernd Schulze, Shin-ichi Tanigawa, and Walter Whiteley SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2591-2611, January 2018. A rigidity theory is developed for bar-joint frameworks in $\mathbb{R}^{d+1}$ whose vertices are constrained to lie...

By Hannah Cairns SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2636-2666, January 2018. The abelian sandpile model is a simple combinatorial model for critical behavior: a chip game on...

By Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2612-2635, January 2018. We initiate the algorithmic study of the following “structured augmentation” question: is it possible to increase...

By Vladimir Kolmogorov SIAM Journal on Computing, Volume 47, Issue 6, Page 2029-2056, January 2018. We consider the recent formulation of the algorithmic Lovász Local Lemma [N. Harvey and J. Vondrák,...

By Adam Smith and Jochen Könemann SIAM Journal on Computing, Volume 47, Issue 5, Page 1807-1808, January 2018. This issue of SICOMP contains six specially selected papers from STOC 2014, the Forty-Sixth Annual ACM Symposium...

By Alexander A. Sherstov SIAM Journal on Computing, Volume 47, Issue 5, Page 1809-1857, January 2018. The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$...

By Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2467-2481, January 2018. In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown...

By Ruta Mehta SIAM Journal on Computing, Volume 47, Issue 5, Page 1858-1887, January 2018. Finding a Nash equilibrium in a two-player normal form game (2-Nash) is one of the most extensively...

By R. Ryan Williams SIAM Journal on Computing, Volume 47, Issue 5, Page 1965-1985, January 2018. We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $n...

By Mark Bun, Jonathan Ullman, and Salil Vadhan SIAM Journal on Computing, Volume 47, Issue 5, Page 1888-1938, January 2018. We show new information-theoretic lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately...

By Benjamin Rossman SIAM Journal on Computing, Volume 47, Issue 5, Page 1986-2028, January 2018. We prove an $n^{\Omega(\log k)}$ lower bound on the $\mathsf{AC^0}$ formula size of Distance $k(n)$ Connectivity for...

By Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking SIAM Journal on Computing, Volume 47, Issue 5, Page 1939-1964, January 2018. We study packing linear programs (LPs) in an online model where the columns are presented to the...

By Sándor Z. Kiss, Csaba Sándor, and Quan-Hui Yang SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2453-2466, January 2018. Let ${\mathbb Z}^{+}$ be the set of positive integers. Let $C_{k}$ denote all subsets of ${\mathbb...

By Mika Göös and Toniann Pitassi SIAM Journal on Computing, Volume 47, Issue 5, Page 1778-1806, January 2018. We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström [STOC 2012, ACM,...

By Tobias Friedrich, Maximilian Katzmann, and Anton Krohmer SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2441-2452, January 2018. Random walks are frequently used in randomized algorithms. We study a derandomized variant of a...

By Bernardo M. Ábrego, Oswin Aichholzer, Silvia Fernández-Merchant, Dan McQuillan, Bojan Mohar, Petra Mutzel, Pedro Ramos, R. Bruce Richter, and Birgit Vogtenhuber SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2482-2492, January 2018. The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of...

By Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2512-2565, January 2018. Seymour's decomposition theorem for regular matroids is a fundamental result with a number of...

By Ben Krause SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2493-2511, January 2018. We extend the main result of Harrow, Kolla, and Schulman---the existence of dimension-free $L^2$-bounds for the...

By Man-Kwun Chiu and Matias Korman SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2566-2590, January 2018. We consider the problem of digitalizing Euclidean line segments from $\mathbb{R}^d$ to $\mathbb{Z}^d$. Christ, Pálvölgyi, and...

By Anthony Nixon, Bernd Schulze, Shin-ichi Tanigawa, and Walter Whiteley SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2591-2611, January 2018. A rigidity theory is developed for bar-joint frameworks in $\mathbb{R}^{d+1}$ whose vertices are constrained to lie...

By Hannah Cairns SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2636-2666, January 2018. The abelian sandpile model is a simple combinatorial model for critical behavior: a chip game on...

By Fedor V. Fomin, Petr A. Golovach, and Dimitrios M. Thilikos SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2612-2635, January 2018. We initiate the algorithmic study of the following “structured augmentation” question: is it possible to increase...

By Vladimir Kolmogorov SIAM Journal on Computing, Volume 47, Issue 6, Page 2029-2056, January 2018. We consider the recent formulation of the algorithmic Lovász Local Lemma [N. Harvey and J. Vondrák,...

By Adam Smith and Jochen Könemann SIAM Journal on Computing, Volume 47, Issue 5, Page 1807-1808, January 2018. This issue of SICOMP contains six specially selected papers from STOC 2014, the Forty-Sixth Annual ACM Symposium...

By Alexander A. Sherstov SIAM Journal on Computing, Volume 47, Issue 5, Page 1809-1857, January 2018. The threshold degree of a Boolean function $f$ is the minimum degree of a real polynomial $p$...

By Martin Grohe, Stephan Kreutzer, Roman Rabinovich, Sebastian Siebertz, and Konstantinos Stavropoulos SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2467-2481, January 2018. In [M. Grohe, S. Kreutzer, and S. Siebertz, J. ACM, 64 (2017), 17] it was shown...

By Ruta Mehta SIAM Journal on Computing, Volume 47, Issue 5, Page 1858-1887, January 2018. Finding a Nash equilibrium in a two-player normal form game (2-Nash) is one of the most extensively...

By R. Ryan Williams SIAM Journal on Computing, Volume 47, Issue 5, Page 1965-1985, January 2018. We present a new randomized method for computing the min-plus product (a.k.a., tropical product) of two $n...

By Mark Bun, Jonathan Ullman, and Salil Vadhan SIAM Journal on Computing, Volume 47, Issue 5, Page 1888-1938, January 2018. We show new information-theoretic lower bounds on the sample complexity of $(\varepsilon, \delta)$-differentially private algorithms that accurately...

By Benjamin Rossman SIAM Journal on Computing, Volume 47, Issue 5, Page 1986-2028, January 2018. We prove an $n^{\Omega(\log k)}$ lower bound on the $\mathsf{AC^0}$ formula size of Distance $k(n)$ Connectivity for...

By Thomas Kesselheim, Klaus Radke, Andreas Tönnis, and Berthold Vöcking SIAM Journal on Computing, Volume 47, Issue 5, Page 1939-1964, January 2018. We study packing linear programs (LPs) in an online model where the columns are presented to the...

By Sándor Z. Kiss, Csaba Sándor, and Quan-Hui Yang SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2453-2466, January 2018. Let ${\mathbb Z}^{+}$ be the set of positive integers. Let $C_{k}$ denote all subsets of ${\mathbb...

By Mika Göös and Toniann Pitassi SIAM Journal on Computing, Volume 47, Issue 5, Page 1778-1806, January 2018. We use critical block sensitivity, a new complexity measure introduced by Huynh and Nordström [STOC 2012, ACM,...

By Tobias Friedrich, Maximilian Katzmann, and Anton Krohmer SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2441-2452, January 2018. Random walks are frequently used in randomized algorithms. We study a derandomized variant of a...

By Colin Cooper, Martin Dyer, Alan Frieze, and Nicolás Rivera SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2398-2420, January 2018. We consider an asynchronous voting process on graphs called discordant voting, which can be described as...

By Edgardo Riquelme and Nicolas Thériault SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2421-2440, January 2018. We provide a symbolic trisection polynomial for Jacobians of genus 2 curves over finite field...

By Michaël Rao and Matthieu Rosenfeld SIAM Journal on Discrete Mathematics, Volume 32, Issue 4, Page 2381-2397, January 2018. A long standing question asks whether $\mathbb{Z}$ is uniformly 2-repetitive, that is, whether or not there...

By Nikhil Bansal, Shashwat Garg, Jesper Nederlof, and Nikhil Vyas SIAM Journal on Computing, Volume 47, Issue 5, Page 1755-1777, January 2018. We present randomized algorithms that solve subset sum and knapsack instances with $n$ items in $O^*(2^{0.86n})$ time,...

By Michael A. Bender, Tsvi Kopelowitz, Seth Pettie, and Maxwell Young SIAM Journal on Computing, Volume 47, Issue 5, Page 1735-1754, January 2018. For decades, randomized exponential backoff has provided a critical algorithmic building block in situations where multiple devices...

By Tim E. Wilson and David R. Wood SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2346-2360, January 2018. An anagram is a word of the form $WP$ where $W$ is a non-empty word and...

By Adam Mammoliti and Thomas Britz SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2361-2380, January 2018. Mubayi's conjecture states that if $\mathcal{F}$ is a family of $k$-sized subsets of $[n] = \{1,\ldots,n\}$...

By Daniel Lokshtanov, Michał Pilipczuk, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2332-2345, January 2018. A vertex subset $S$ in a graph $G$ is a dominating set if every vertex not...

By Catherine Erbes, Michael Ferrara, Ryan R. Martin, and Paul Wenger SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2313-2331, January 2018. A graphic sequence $\pi$ is potentially $H$-graphic if there is some realization of $\pi$ that contains...

By Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, and Ignasi Sau SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2302-2312, January 2018. Let $W_t$ denote the wheel on t+1 vertices. We prove that for every integer $t...

By Bart M. P. Jansen and Marcin Pilipczuk SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2258-2301, January 2018. The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an...

By Arseniy Akopyan and Erel Segal-Halevi SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2242-2257, January 2018. Inside a two-dimensional region (``cake''), there are $m$ nonoverlapping tiles of a certain kind (``toppings''). We...

By Sihuang Hu, Itzhak Tamo, and Ofer Shayevitz SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2229-2241, January 2018. We prove an upper bound on the Shannon capacity of a graph via a linear programming...

By Ramin Javadi and Gholamreza Omidi SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2217-2228, January 2018. For given simple graphs $G_1$ and $G_2$, the size Ramsey number $\hat{R}(G_1,G_2)$ is the smallest positive...

By Michael Anastos SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2194-2216, January 2018. In this paper, we study the connectivity properties of the random subgraph of the n-cube...

By Takeharu Shiraga, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2180-2193, January 2018. The rotor-router model is a deterministic process analogous to a simple random walk on a graph,...

By T-H. Hubert Chan, Shuguang Hu, and Shaofeng H.-C. Jiang SIAM Journal on Computing, Volume 47, Issue 4, Page 1705-1734, January 2018. We achieve a (randomized) polynomial-time approximation scheme (PTAS) for the Steiner forest problem in doubling metrics. Before...

By Linyuan Lu and Zhiyu Wang SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2172-2179, January 2018. For any $r\geq 2$ and $k\geq 3$, the $r$-color size-Ramsey number $\hat R(\mathcal{G},r)$ of a $k$-uniform...

By Sihuang Hu, Nir Weinberger, and Ofer Shayevitz SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2161-2171, January 2018. We investigate the maximal asymptotic rates of length-$n$ binary codes with VC-dimension at most $dn$ and...

By Andreas Emil Feldmann, Wai Shing Fung, Jochen Könemann, and Ian Post SIAM Journal on Computing, Volume 47, Issue 4, Page 1667-1704, January 2018. Graphs with bounded highway dimension were introduced by Abraham et al. [Proceedings of SODA 2010, pp. 782--793]...

By Chandra Chekuri, Alina Ene, and Marcin Pilipczuk SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2134-2160, January 2018. We study the problem of routing symmetric demand pairs in planar digraphs. The input consists...

By Sagnik Mukhopadhyay, Jaikumar Radhakrishnan, and Swagato Sanyal SIAM Journal on Computing, Volume 47, Issue 4, Page 1644-1666, January 2018. Saks and Wigderson [in Proceedings of the $27$th FOCS, IEEE Computer Society, Los Alamitos, CA, 1986,...

By Chandra Chekuri and Anastasios Sidiropoulos SIAM Journal on Computing, Volume 47, Issue 4, Page 1610-1643, January 2018. The Euler genus of a graph is a fundamental and well-studied parameter in graph theory and topology....

By Barbora Duník and Robert Lukoťka SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2094-2114, January 2018. We prove that every simple bridgeless cubic graph with $n \ge 8$ vertices has a traveling...

By Alan Frieze, Wesley Pegden, and Gregory B. Sorkin SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2115-2133, January 2018. We determine, asymptotically in $n$, the distribution and mean of the weight of a minimum-weight $k$-clique...

By Carlos A. Alfaro, Alan Arroyo, Marek Derňár, and Bojan Mohar SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2080-2093, January 2018. Motivated by a problem asked by Richter and by the long standing Harary--Hill conjecture, we study...

By Leo van Iersel and Vincent Moulton SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2047-2066, January 2018. An important problem in evolutionary biology is to reconstruct the evolutionary history of a set $X$...

By Venkata Gandikota, Badih Ghazi, and Elena Grigorescu SIAM Journal on Computing, Volume 47, Issue 4, Page 1547-1584, January 2018. Establishing the complexity of bounded distance decoding for Reed--Solomon codes is a fundamental open problem in...

By Antoine Deza, Asaf Levin, Syed M. Meesum, and Shmuel Onn SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2067-2079, January 2018. We introduce and study the problem of optimizing arbitrary functions over degree sequences of hypergraphs and...

By Sarah Cannon, Sarah Miracle, and Dana Randall SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1966-1992, January 2018. We study rectangular dissections of an $n \times n$ lattice region into rectangles of area...

By Bao-Xuan Zhu SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1993-2010, January 2018. In this paper, we present some criteria for the 2-$q$-log-convexity and 3-$q$-log-convexity of combinatorial sequences, which...

By T-H. Hubert Chan, Fei Chen, Xiaowei Wu, and Zhichao Zhao SIAM Journal on Computing, Volume 47, Issue 4, Page 1529-1546, January 2018. Motivated by online advertisement and exchange settings, greedy randomized algorithms for the maximum matching problem have been...

By Haim Kaplan, Wolfgang Mulzer, Liam Roditty, and Paul Seiferth SIAM Journal on Computing, Volume 47, Issue 4, Page 1585-1609, January 2018. Let $P \subset \mathbb{R}^2$ be a planar $n$-point set such that each point $p \in P$ has...

By Guillermo Pineda-Villavicencio, Julien Ugon, and David Yost SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 2011-2046, January 2018. We define the excess degree $\xi(P)$ of a $d$-polytope $P$ as $2f_1-df_0$, where $f_0$ and $f_1$...

By Petr Hliněný and Carsten Thomassen SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1962-1965, January 2018. We prove that it is NP-hard to determine whether the crossing number of an input graph...

By Maximilien Gadouleau SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1922-1945, January 2018. The properties of finite dynamical systems (FDSs) have been investigated in the context of coding theoretic...

By Reuven Bar-Yehuda, Erez Kantor, Shay Kutten, and Dror Rawitz SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1903-1921, January 2018. The dynamic content distribution problem addresses the trade-off between storage and delivery costs in modern virtual...

By Manuel Aprile, Alfonso Cevallos, and Yuri Faenza SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1857-1886, January 2018. $2$-level polytopes naturally appear in several areas of pure and applied mathematics, including combinatorial optimization, polyhedral...

By Yanping Wang, Weiguo Zhang, and Zhengbang Zha SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1946-1961, January 2018. Permutation polynomials over finite fields constitute an active research area. Permutation trinomials attract researchers' interest due...

By Harry H. Y. Huang and Larry X. W. Wang SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1887-1902, January 2018. In this paper, we are concerned with counting corners of core partitions. We introduce the...

By Stefan Kratsch SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1806-1839, January 2018. In the vertex cover problem we are given a graph $G=(V,E)$ and an integer $k$ and...

By María A. Hernández Cifre, David Iglesias, and Jesús Yepes Nicolás SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1840-1856, January 2018. The Brunn--Minkowski inequality states that the volume of compact sets $K,L\subset\mathbb{R}^n$ satisfies $\mathrm{vol}(K+L)^{1/n}\geq\mathrm{vol}(K)^{1/n}+\mathrm{vol}(L)^{1/n}$. In this paper...

By Deeparnab Chakrabarty, Alina Ene, Ravishankar Krishnaswamy, and Debmalya Panigrahi SIAM Journal on Computing, Volume 47, Issue 4, Page 1505-1528, January 2018. We present the first online algorithms for the nonuniform, multicommodity buy-at-bulk (MC-BB) network design problem. Our competitive...

By Ken-ichi Kawarabayashi and Yusuke Kobayashi SIAM Journal on Computing, Volume 47, Issue 4, Page 1483-1504, January 2018. We study the following all-or-nothing multicommodity flow problem in planar graphs: Input: A graph $G$ with $n$...

By Ahmad Abdi and Kanstantsin Pashkovich SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1750-1774, January 2018. For an integer $n\geq 3$, the clutter $\Delta_n:=\big\{\{1,2\},\{1,3\},\ldots,\{1,n\},\{2,3,\ldots,n\}\big\}$ is called a delta of dimension $n$, whose...

By Zdeněk Dvořák and Bernard Lidický SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1775-1805, January 2018. Aksenov proved that in a planar graph $G$ with at most one triangle, every precoloring of...

By Fu Li, Iddo Tzameret, and Zhengyu Wang SIAM Journal on Computing, Volume 47, Issue 4, Page 1424-1462, January 2018. Does every Boolean tautology have a short propositional-calculus proof? Here, a propositional-calculus (i.e., Frege) proof is any...

By Gaetan Bisson and Mehdi Tibouchi SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1741-1749, January 2018. A permutation rational function $f\in\mathbb{F}\/_q(x)$ is a rational function that induces a bijection on $\mathbb{F}\/_q$, that...

By V. Arvind, Partha Mukhopadhyay, Prajakta Nimbhorkar, and Yadu Vasudev SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1721-1740, January 2018. Let $G =\langle S\rangle$ be a solvable permutation group given as input by the generating set...

By Clément L. Canonne, Themis Gouleakis, and Ronitt Rubinfeld SIAM Journal on Computing, Volume 47, Issue 4, Page 1373-1423, January 2018. In many situations, sample data is obtained from a noisy or imperfect source. In order to address...

By Niv Buchbinder, Joseph SeffiNaor, and Roy Schwartz SIAM Journal on Computing, Volume 47, Issue 4, Page 1463-1482, January 2018. The \sf Multiway-Cut problem is a fundamental graph partitioning problem in which the objective is to...

By Łukasz Kowalik, Juho Lauri, and Arkadiusz Socała SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1672-1705, January 2018. The Rainbow $k$-Coloring problem asks whether the edges of a given graph can be colored in...

By Christoph Glanzer, Robert Weismantel, and Rico Zenklusen SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1706-1720, January 2018. Let $A \in \mathbb{Z}^{m \times n}$ be a matrix with $\mathrm{rank}(A) = n$, whose $(n \times...

By Akanksha Agrawal, Daniel Lokshtanov, Diptapriyo Majumdar, Amer E. Mouawad, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1619-1643, January 2018. A key result in the field of kernelization, a subfield of parameterized complexity, states that the...

By Hoang Dau and Olgica Milenkovic SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1644-1671, January 2018. Many code families such as low-density parity-check codes, fractional repetition codes, batch codes, and private information...

By Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, and Andrew Morgan SIAM Journal on Computing, Volume 47, Issue 4, Page 1339-1372, January 2018. We study the computational power of deciding whether a given truth table can be described by a...

By Vitaly Feldman, Will Perkins, and Santosh Vempala SIAM Journal on Computing, Volume 47, Issue 4, Page 1294-1338, January 2018. The problem of identifying a planted assignment given a random $k$-satisfiability ($k$-SAT) formula consistent with the assignment...

By Lisa Espig, Alan Frieze, and Michael Krivelevich SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1585-1618, January 2018. We first consider the following problem. We are given a fixed perfect matching $M$ of $[n]$...

By Peter Keevash and Liana Yepremyan SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1577-1584, January 2018. Aharoni and Berger conjectured that in any bipartite multigraph that is properly edge-colored by $n$ colors...

By Nicole Megow and José Verschae SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1541-1571, January 2018. We study scheduling problems on a machine with varying speed. Assuming a known speed function we...

By Isabella Novik SIAM Journal on Discrete Mathematics, Volume 32, Issue 3, Page 1572-1576, January 2018. What is the maximum number of vertices that a centrally symmetric $2$-neighborly polytope of dimension $d$...

By Mohammad Hossein Bateni, Mohammad Taghi Hajiaghayi, and Vahid Liaghat SIAM Journal on Computing, Volume 47, Issue 4, Page 1275-1293, January 2018. Moss and Rabani study constrained node-weighted Steiner tree problems with two independent weight values associated with each...

By Cláudio L. Lucchesi, Marcelo H. de Carvalho, Nishad Kothari, and U. S. R. Murty SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1478-1504, January 2018. A cut $C:=\partial (X)$ of a matching covered graph $G$ is a separating...

By Michael Anastos and Joseph Briggs SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1505-1539, January 2018. Consider a directed analogue of the random graph process on $n$ vertices, where the $n(n-1)$ edges...

By Eden Chlamtáč, Michael Dinitz, Christian Konrad, Guy Kortsarz, and George Rabanca SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1458-1477, January 2018. The densest $k$-subgraph (D$k$S) problem and its corresponding minimization problem smallest $p$-edge subgraph (S$p$ES) have come...

By Costis Daskalakis, Yael Kalai, and Sandy Irani SIAM Journal on Computing, Volume 47, Issue 3, Page 888-889, January 2018. This section of SICOMP contains 11 specially selected papers from the Forty-seventh Annual ACM Symposium on Theory...

By Siddharth Barman SIAM Journal on Computing, Volume 47, Issue 3, Page 960-981, January 2018. We present algorithmic applications of an approximate version of Carathéodory's theorem. The theorem states that given a...

By Richard Cole and Vasilis Gkatzelis SIAM Journal on Computing, Volume 47, Issue 3, Page 1211-1236, January 2018. We study the problem of allocating a set of indivisible items among agents with additive valuations, with...

By Arturs Backurs and Piotr Indyk SIAM Journal on Computing, Volume 47, Issue 3, Page 1087-1097, January 2018. The edit distance (a.k.a. the Levenshtein distance) between two strings is defined as the minimum number...

By Scott Aaronson and Andris Ambainis SIAM Journal on Computing, Volume 47, Issue 3, Page 982-1038, January 2018. We achieve essentially the largest possible separation between quantum and classical query complexities. We do so using...

By Ben Cousins and Santosh Vempala SIAM Journal on Computing, Volume 47, Issue 3, Page 1237-1273, January 2018. We present an $O^*(n^3)$ randomized algorithm for estimating the volume of a well-rounded convex body (e.g., $K\subseteq\mathbb{R}^n$...

By Aviad Rubinstein SIAM Journal on Computing, Volume 47, Issue 3, Page 917-959, January 2018. We prove that finding an $\epsilon$-approximate Nash equilibrium is $\mathsf{PPAD}$--complete for constant $\epsilon$ and a particularly simple...

By Nir Bitansky, Ran Canetti, Sanjam Garg, Justin Holmgren, Abhishek Jain, Huijia Lin, Rafael Pass, Sidharth Telang, and Vinod Vaikuntanathan SIAM Journal on Computing, Volume 47, Issue 3, Page 1123-1210, January 2018. We show how to construct indistinguishability obfuscation (\bf iO) for RAM programs with bounded space, assuming \bf...

By Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu SIAM Journal on Computing, Volume 47, Issue 3, Page 1098-1122, January 2018. Due to the lack of unconditional polynomial lower bounds, it is now in fashion to prove conditional...

By Nikhil Bansal, Anupam Gupta, and Guru Guruganesh SIAM Journal on Computing, Volume 47, Issue 3, Page 1039-1055, January 2018. We consider the maximum independent set problem on sparse graphs with maximum degree $d$. We show that...

By Nitish Korula, Vahab Mirrokni, and Morteza Zadimoghaddam SIAM Journal on Computing, Volume 47, Issue 3, Page 1056-1086, January 2018. In the submodular welfare maximization (SWM) problem, the input consists of a set of $n$ items, each...

By Alexandr Andoni, Robert Krauthgamer, and Ilya Razenshteyn SIAM Journal on Computing, Volume 47, Issue 3, Page 890-916, January 2018. An outstanding open question posed by Guha and Indyk in 2006 asks us to characterize metric spaces...

By Sayan Bhattacharya, Monika Henzinger, and Giuseppe F. Italiano SIAM Journal on Computing, Volume 47, Issue 3, Page 859-887, January 2018. We present the first deterministic data structures for maintaining approximate minimum vertex cover and maximum matching...

By Anne-Maria Ernvall-Hytönen and Esa V. Vesalainen SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1441-1457, January 2018. We show that for every $\ell>1$, there is a counterexample to the $\ell$-modular secrecy function conjecture...

By Petr Hliněný SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1425-1440, January 2018. The path-width of matroids naturally generalizes the better known parameter of path-width for graphs and is...

By D. P. Bourne, D. Cushing, S. Liu, F. Münch, and N. Peyerimhoff SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1408-1424, January 2018. We study the Ollivier--Ricci curvature of graphs as a function of the chosen idleness. We show...

By J. Chappelon, L. Martínez-Sandoval, L. Montejano, L. P. Montejano, and J. L. Ramírez Alfonsín SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1351-1363, January 2018. Let $k,d,\lambda \geqslant 1$ be integers with $d\geqslant \lambda $ and let $X$ be a finite...

By Hiệp Hàn and Andrea Jiménez SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1364-1368, January 2018. Given integers $r, k \geq2$ let $\kappa_{r,k+1}(G)$ denote the number of distinct edge colorings of $G$...

By Andreas Alpers and Peter Gritzmann SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1369-1399, January 2018. Superresolution imaging aims at improving the resolution of an image by enhancing it with other images...

By Konstanty Junosza-Szaniawski, Paweł Rzaͅżewski, Joanna Sokół, and Krzysztof Weͅsek SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1335-1350, January 2018. In this paper we give a family of online algorithms for the classical coloring and the...

By Michael Elkin, Arnold Filtser, and Ofer Neiman SIAM Journal on Computing, Volume 47, Issue 3, Page 829-858, January 2018. Metric data structures (distance oracles, distance labeling schemes, routing schemes) and low-distortion embeddings provide a powerful algorithmic...

By Kevin Hendrey SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1400-1407, January 2018. By considering graphs as discrete analogues of Riemann surfaces, Baker and Norine [Adv. Math., 215 (2007),...

By Jiabao Lin and Hanpin Wang SIAM Journal on Computing, Volume 47, Issue 3, Page 798-828, January 2018. Holant problem is a general framework to study the computational complexity of counting problems. We prove a...

By Mehtaab Sawhney and David Stoner SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1296-1304, January 2018. A numerical semigroup $S$ is called cyclotomic if its corresponding numerical semigroup polynomial, $P_S(x)=(1-x)\sum_{s\in S}x^s$, is...

By Florent R. Madelaine and Barnaby D. Martin SIAM Journal on Computing, Volume 47, Issue 3, Page 769-797, January 2018. The complexity of the model checking problem for various fragments of first-order logic (FO) has attracted much...

By Tobias Friedrich and Anton Krohmer SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1314-1334, January 2018. Large real-world networks are typically scale-free. Recent research has shown that such graphs are described best...

By Xiaofeng Gu SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1305-1313, January 2018. Rigidity, arising in discrete geometry, is the property of a structure that does not flex. Laman...

By Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, and Elena Grigorescu SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1265-1295, January 2018. Testing membership in lattices is of practical relevance, with applications to integer programming, error detection in...

By Ilkyoo Choi, Chun-Hung Liu, and Sang-il Oum SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1209-1228, January 2018. For nonnegative integers $k, d_1, \ldots, d_k$, a graph is $(d_1, \ldots, d_k)$-colorable if its vertex...

By Pradeesha Ashok, Aditi Dudeja, Sudeshna Kolay, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1189-1208, January 2018. Conflict-free coloring of hypergraphs is a very well studied question of theoretical and practical interest. For...

By Henning Bruhn, Matthias Heinlein, and Felix Joos SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1246-1260, January 2018. A key feature of Simonovits' proof of the classic Erdös--Pósa theorem is a simple subgraph of...

By Dániel Korándi SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1261-1264, January 2018. The $t$-colored rainbow saturation number ${rsat}_t(n,F)$ is the minimum size of a $t$-edge-colored graph on $n$...

By Roee David and Uriel Feige SIAM Journal on Computing, Volume 47, Issue 3, Page 755-768, January 2018. For a simple (unbiased) random walk on a connected graph with $n$ vertices, the cover time (the...

By Pu Gao SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1159-1188, January 2018. This paper is a continuation of previous results on the stripping number of a random uniform...

By Bo Lin and Ruriko Yoshida SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1229-1245, January 2018. In a metric space, the Fermat--Weber points of a sample are statistics to measure the central...

By Allan Lo and Yi Zhao SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1154-1158, January 2018. Let $r\ge 3$. Given an $r$-graph $H$, the minimum codegree $\delta_{r-1}(H)$ is the largest integer $t$...

By Peter Nelson and Jorn van der Pol SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1145-1153, January 2018. A matroid is Ingleton if all quadruples of subsets of its ground set satisfy Ingleton's inequality....

By Maria-Florina Balcan and Nicholas J. A. Harvey SIAM Journal on Computing, Volume 47, Issue 3, Page 703-754, January 2018. Submodular functions are discrete functions that model laws of diminishing returns and enjoy numerous algorithmic applications. They...

By Donald K. Wagner SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1139-1144, January 2018. It is shown that a binary matroid is graphic if and only if it does not...

By Daniel Lokshtanov, Dániel Marx, and Saket Saurabh SIAM Journal on Computing, Volume 47, Issue 3, Page 675-702, January 2018. A central problem in parameterized algorithms is to obtain algorithms with running time $f(k)\cdot n^{O(1)}$ such that...

By Maria Chudnovsky and Juraj Stacho SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1111-1138, January 2018. In this paper, we study 3-colorable graphs having no induced 8-vertex path and no induced cycles...

By David Jekel, Avi Levy, Will Dana, Austin Stromme, and Collin Litterell SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1040-1110, January 2018. We propose an algebraic framework for generalized graph Laplacians which unifies the study of resistor networks,...

By Zoltán Füredi and Ida Kantor SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1016-1028, January 2018. Every graph $G=(V,E)$ is an induced subgraph of some Kneser graph of rank $k$, i.e., there...

By Samantha Dahlberg and Stephanie van Willigenburg SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1029-1039, January 2018. We compute an explicit $e$-positive formula for the chromatic symmetric function of a lollipop graph, $L_{m,n}$....

By Zhiyi Huang, Yishay Mansour, and Tim Roughgarden SIAM Journal on Computing, Volume 47, Issue 3, Page 651-674, January 2018. We study the problem of setting a price for a potential buyer with a valuation drawn from...

By Surender Baswana, Manoj Gupta, and Sandeep Sen SIAM Journal on Computing, Volume 47, Issue 3, Page 617-650, January 2018. We present an algorithm for maintaining a maximal matching in a graph under addition and deletion of...

By Sean Cleary and Roland Maio SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 1003-1015, January 2018. There are no known efficient algorithms to calculate distance in the one-skeleta of associahedra, a problem...

By Danny Nguyen and Igor Pak SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 986-1002, January 2018. We extend the Barvinok--Woods algorithm for enumerating projections of integer points in polytopes to unbounded polyhedra....

By Fedor V. Fomin, Daniel Lokshtanov, S. M. Meesum, Saket Saurabh, and Meirav Zehavi SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 966-985, January 2018. For a target rank $r$, the rigidity of a matrix $A$ over a field $\mathbb{F}$ is...

By Beka Ergemlidze, Ervin Györi, and Abhishek Methuku SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 933-950, January 2018. Gyárfás, Györi, and Simonovits [J. Comb., 7 (2016), pp. 205--216] proved that if a $3$-uniform hypergraph...

By Mikhail Belkin, Luis Rademacher, and James Voss SIAM Journal on Computing, Volume 47, Issue 2, Page 547-615, January 2018. The eigendecomposition of quadratic forms (symmetric matrices) guaranteed by the spectral theorem is a foundational result in...

By Maria Chudnovsky and Vaidy Sivaraman SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 951-955, January 2018. The complexity of testing whether a graph contains an induced odd cycle of length at least...

By Jie Han SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 919-932, January 2018. In this paper we study some variants of Dirac-type problems in hypergraphs. First, we show that...

By Jian Cheng, You Lu, Rong Luo, and Cun-Quan Zhang SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 956-965, January 2018. Converting modulo flows into integer-valued flows is one of the most critical steps in the study...

By Laurent Beaudou, Peter Dankelmann, Florent Foucaud, Michael A. Henning, Arnaud Mary, and Aline Parreau SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 902-918, January 2018. The metric dimension of a graph is the minimum size of a set of vertices such...

By Geevarghese Philip, Ashutosh Rai, and Saket Saurabh SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 882-901, January 2018. Feedback Vertex Set (FVS) is one of the most well-studied problems in the realm of parameterized...

By Dániel Gerbner, Balázs Keszegh, Gábor Mészáros, Balázs Patkós, and Máté Vizer SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 864-881, January 2018. We study combinatorial parameters of a recently introduced bootstrap percolation problem in finite projective planes. We...

By Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett SIAM Journal on Computing, Volume 47, Issue 2, Page 524-546, January 2018. Non-malleable codes provide a useful and meaningful security guarantee in situations where traditional error-correction (and even error-detection)...

By Georg Gottlob and Enrico Malizia SIAM Journal on Computing, Volume 47, Issue 2, Page 456-492, January 2018. The hypergraph duality problem Dual is defined as follows: given two simple hypergraphs $\mathcal{G}$ and $\mathcal{H}$, decide...

By Elad Haramaty, Chin Ho Lee, and Emanuele Viola SIAM Journal on Computing, Volume 47, Issue 2, Page 493-523, January 2018. Let $D$ be a $b$-wise independent distribution over $\{0,1\}^m$. Let $E$ be the “noise” distribution over...

By Wojciech Golab, Xiaozhou SteveLi, Alejandro López-Ortiz, and Naomi Nishimura SIAM Journal on Computing, Volume 47, Issue 2, Page 420-455, January 2018. The $k$-atomicity property can be used to describe the consistency of data operations in large distributed storage...

By Vida Dujmović, Gwenaël Joret, Pat Morin, Sergey Norin, and David R. Wood SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 839-863, January 2018. This paper studies graphs that have two tree decompositions with the property that every bag from...

By Alexander A. Sherstov SIAM Journal on Computing, Volume 47, Issue 2, Page 367-419, January 2018. We study the problem of compressing interactive communication to its information content $I$, defined as the amount...

By Hiệp Hàn, Vojtěch Rödl, and Tibor Szabó SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 826-838, January 2018. We investigate the smallest possible minimum degree of $r$-color minimal Ramsey graphs for the $k$-clique. In...

By Simon Macourt SIAM Journal on Discrete Mathematics, Volume 32, Issue 2, Page 815-825, January 2018. We give a new bound on the number of collinear triples for two arbitrary subsets of...

By Moran Feldman and Rico Zenklusen SIAM Journal on Computing, Volume 47, Issue 2, Page 330-366, January 2018. During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of...

By Tri Lai SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 783-814, January 2018. Proctor's work on staircase plane partitions yields an enumeration of lozenge tilings of a halved hexagon...

By Benoit Larose and Mark Siggers SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 728-749, January 2018. We find a set of generators of the variety of reflexive digraphs admitting $k-{NU}$ polymorphisms. We...

By Herbert Edelsbrunner and Mabel Iglesias-Ham SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 750-782, January 2018. Motivated by biological questions, we study configurations of equal spheres that neither pack nor cover. Placing...

By David Coudert and Guillaume Ducoffe SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 682-694, January 2018. We study the complexity of decomposing a graph by means of clique separators. This common algorithmic...

By Chris Dowden, Mihyun Kang, and Philipp Sprüssel SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 695-727, January 2018. For integers $g,m \geq 0$ and $n>0$, let $S_{g}(n,m)$ denote the graph taken uniformly at random...

By Till Fluschnik, Danny Hermelin, André Nichterlein, and Rolf Niedermeier SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 656-681, January 2018. The composition technique is a popular method for excluding polynomial-size problem kernels for NP-hard parameterized problems....

By Lucas Boczkowski, Yuval Peres, and Perla Sousi SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 624-655, January 2018. Let $X$ be a lazy random walk on a graph $G$. If $G$ is undirected, then...

By Kashyap Dixit, Sofya Raskhodnikova, Abhradeep Thakurta, and Nithin Varma SIAM Journal on Computing, Volume 47, Issue 2, Page 295-329, January 2018. Property testers form an important class of sublinear-time algorithms. In the standard property testing model, an algorithm...

By Megumi Asada, Florian Frick, Vivek Pisharody, Maxwell Polevy, David Stoner, Ling Hei Tsang, and Zoe Wellner SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 591-610, January 2018. We treat problems of fair division, their various interconnections, and their relations to Sperner's lemma and...

By Michael Krivelevich SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 611-623, January 2018. We show that every locally sparse graph contains a linearly sized expanding subgraph. For constants c_1>c_2>1,...

By Kristóf Bérczi, Satoru Iwata, Jun Kato, and Yutaro Yamaguchi SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 560-590, January 2018. The Dulmage--Mendelsohn decomposition (or the DM-decomposition) gives a unique partition of the vertex set of a...

By He Huang, Binzhou Xia, and Sanming Zhou SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 548-559, January 2018. Given a graph $\Gamma$, a subset $C$ of $V(\Gamma)$ is called a perfect code in $\Gamma$...

By Stéphane Bessy, Mitre C. Dourado, Lucia D. Penso, and Dieter Rautenbach SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 543-547, January 2018. Kanté and Nourine [SIAM J. Discrete Math., 30 (2016), pp. 311--326] present a polynomial time algorithm...

By Mohit Singh and László A. Végh SIAM Journal on Computing, Volume 47, Issue 1, Page 270-293, January 2018. We investigate problems addressing combined connectivity augmentation and orientations settings. We give a polynomial-time 6-approximation algorithm for...

By Mika Göös, Rahul Jain, and Thomas Watson SIAM Journal on Computing, Volume 47, Issue 1, Page 241-269, January 2018. We exhibit an $n$-node graph whose independent set polytope requires extended formulations of size exponential in $\Omega(n/\log...

By Louis Esperet, Rémi de Joannis de Verclos, Tien-Nam Le, and Stéphan Thomassé SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 534-542, January 2018. It was conjectured by Jaeger et al. in 1992 that for any prime number $p$, there...

By Hongliang Lu, Yan Wang, and Xingxing Yu SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 522-533, January 2018. The minimum codegree threshold for a perfect matching in a $k$-graph with $n$ vertices was...

By Artur Czumaj and Peter Davies SIAM Journal on Computing, Volume 47, Issue 1, Page 218-240, January 2018. In this paper we improve the deterministic complexity of two fundamental communication primitives in the classical model...

By Jianfeng Hou, Shufei Wu, Qinghou Zeng, and Wenxing Zhu SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 505-521, January 2018. Let $r\ge 3$ and $k\ge 2$ be fixed integers. Bollobás and Scott conjectured that every $r$-uniform...

By Miroslav Rada and Michal Černý SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 455-473, January 2018. We design a new algorithm, called Incremental Enumeration (IncEnu), for the enumeration of full-dimensional cells of...

By William Y. C. Chen and Lisa H. Sun SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 474-504, January 2018. We present an algorithmic approach to the verification of identities on multiple theta functions in the...

By Hamed Hatami, Kaave Hosseini, and Shachar Lovett SIAM Journal on Computing, Volume 47, Issue 1, Page 208-217, January 2018. Let $f:\{0,1\}^n\to\{0,1\}$ be a boolean function. Its associated XOR function is the two-party function $f_{\oplus}(x,y)=f(x\oplus y)$. We...

By Yoshiharu Kohayakawa, Sang June Lee, Carlos Gustavo Moreira, and Vojtěch Rödl SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 410-449, January 2018. A set $S$ of natural numbers is a Sidon set if all the sums $s_1+s_2$ with...

By Jun Wang and Huajun Zhang SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 372-381, January 2018. Let $X_{1}, \ldots,X_m$ be $m$ pairwise disjoint sets with the same size $n$, and let...

By António Gira͂o and Kamil Popielarz SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 450-454, January 2018. In this note, we prove that for every integer $k$, there exist constants $g_{1}(k)$ and $g_{2}(k)$...

By Nicolas Bousquet, Jean Daligault, and Stéphan Thomassé SIAM Journal on Computing, Volume 47, Issue 1, Page 166-207, January 2018. Let $G=(V,E)$ be a graph on $n$ vertices and $R$ be a set of pairs of vertices...

By Shuya Chiba and Tomoki Yamashita SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 394-409, January 2018. In this paper, we give the following result: If $D$ is a digraph of order $n$,...

By Hongliang Lu and Xingxing Yu SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 382-393, January 2018. For any positive integer $m$, let $[m]:=\{1,\ldots,m\}$. Let $n,k,t$ be positive integers. Aharoni and Howard conjectured...

By David Hartvigsen SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 320-351, January 2018. A (simple) $k$-matching in a graph is a subgraph all of whose nodes have degree at...

By Stephen R. Chestnut, Robert Hildebrand, and Rico Zenklusen SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 352-371, January 2018. The recent paper A Quantitative Doignon-Bell-Scarf Theorem by Aliev et al. [Combinatorica, 37 (2017), pp. 313--332]...

By Jie Ma and Bo Ning SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 296-319, January 2018. In this paper we determine the chromatic number of graphs with two odd cycle lengths. Let...

By Dániel Gerbner, Balázs Keszegh, Cory Palmer, and Balázs Patkós SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 266-279, January 2018. Let $L$ be a set of positive integers. We call a (directed) graph $G$ an $L$-cycle...

By Daniel Pellicer and Gordon Ian Williams SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 249-265, January 2018. In this paper we exhibit the first infinite family of abstract 4-polytopes whose connection groups...

By Benny Sudakov and Pedro Vieira SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 280-295, January 2018. A family $\mathcal A$ of subsets of an $n$-element set is called an eventown (resp., oddtown)...

By Yiannis Giannakopoulos and Elias Koutsoupias SIAM Journal on Computing, Volume 47, Issue 1, Page 121-165, January 2018. We develop a general duality-theory framework for revenue maximization in additive Bayesian auctions. The framework extends linear...

By Kyungyong Lee, Li Li, and Nicholas A. Loehr SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 191-232, January 2018. The $q,t$-Catalan numbers $C_n(q,t)$ are polynomials in $q$ and $t$ that reduce to the ordinary Catalan...

By Alexander Hoyer and Robin Thomas SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 233-248, January 2018. We prove an ear-decomposition theorem for 4-edge-connected graphs and use it to prove that for every...

By Bobby Shen SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 173-190, January 2018. We consider a family of integer linear programs in which the coefficients of the constraints and...

By Gwenaël Joret and David R. Wood SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 123-147, January 2018. We prove that every connected graph $G$ with $m$ edges contains a set $X$ of at...

By Surender Baswana, Keerti Choudhary, and Liam Roditty SIAM Journal on Computing, Volume 47, Issue 1, Page 80-95, January 2018. Let $G$ be a directed graph with $n$ vertices, $m$ edges, and a designated source vertex $s$....

By Amit Daniely, Michael Schapira, and Gal Shahaf SIAM Journal on Computing, Volume 47, Issue 1, Page 96-120, January 2018. Algorithmic mechanism design (AMD) studies the delicate interplay between computational efficiency, truthfulness, and optimality. We focus on...

By Mathew C. Francis, Dalu Jacob, and Satyabrata Jana SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 148-172, January 2018. A matching $M$ in a graph $G$ is said to be uniquely restricted if there is...

By Selçuk Kavut, Subhamoy Maitra, and Ferruh Özbudak SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 106-122, January 2018. Construction of Boolean functions on an odd number of variables with nonlinearity exceeding the bent concatenation...

By Benny Applebaum and Shachar Lovett SIAM Journal on Computing, Volume 47, Issue 1, Page 52-79, January 2018. Suppose that you have $n$ truly random bits $x=(x_1,\ldots,x_n)$ and you wish to use them to generate...

By Zdeněk Dvořák and Bernard Lidický SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 94-105, January 2018. Dvořák, Král', and Thomas [Three-Coloring Triangle-Free Graphs on Surfaces IV. Bounding Face Sizes of 4-Critical Graphs,...

By Tyler Seacrest and Francis Edward Su SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 1-28, January 2018. Products of simplices, called simplotopes, and their triangulations arise naturally in algorithmic applications in game theory...

By Sunil Arya, Guilherme D. da Fonseca, and David M. Mount SIAM Journal on Computing, Volume 47, Issue 1, Page 1-51, January 2018. In the polytope membership problem, a convex polytope $K$ in $\mathbb{R}^d$ is given, and the objective is...

By Jaroslaw Byrka and Aravind Srinivasan SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 44-63, January 2018. We present improved approximation algorithms in stochastic optimization. We prove that the multistage stochastic versions of...

By Fatemeh Mohammadi, Caroline Uhler, Charles Wang, and Josephine Yu SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 64-93, January 2018. A graphical model encodes conditional independence relations via the Markov properties. For an undirected graph these...

By Jiaao Li, Xinmin Hou, Miaomiao Han, and Hong-Jian Lai SIAM Journal on Discrete Mathematics, Volume 32, Issue 1, Page 29-43, January 2018. A mod $(2p+1)$-orientation $D$ is an orientation of $G$ such that $d_D^+(v)-d_D^-(v)\equiv 0 \pmod {2p+1}$ for...

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.

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.

The prize recognizes students for outstanding solutions to real world math problems. It is awarded to two 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.

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.

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 will first be awarded in 2020, and 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.

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.

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

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.

The SIAM Outstanding Paper Prizes bring attention to papers published in SIAM journals. Three awards are 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.

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!

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.

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.

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

We use cookies and other tracking technologies to make sure you get the best experience on our website.
Learn MoreOkay