By Luca Becchetti, Andrea E. Clementi, Emanuele Natale, Francesco Pasquale, and Luca TrevisanSIAM Journal on Computing, Volume 49, Issue 4, Page 821-864, January 2020. Given an underlying graph, we consider the following dynamics: Initially, each node locally chooses a value in...
By Pavol Hell, Jing Huang, Ross M. McConnell, and Arash RafieySIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1710-1724, January 2020. We unify several seemingly different graph and digraph classes under one umbrella. These classes are...
Oak Ridge, TN, United States
North Wales, PA, United States
Sunnyvale, CA, United States, United States
By Matthew Coulson and Guillem PerarnauSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1670-1692, January 2020. A famous theorem of Dirac states that any graph on $n$ vertices with minimum degree at...
By Sungjin Im, Shi Li, and Benjamin MoseleySIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1649-1669, January 2020. In this paper we consider one of the most basic scheduling problems where jobs have their...
By Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, and David R. WoodSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1693-1709, January 2020. We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if...
By William M. Hoza and David ZuckermanSIAM Journal on Computing, Volume 49, Issue 4, Page 811-820, January 2020. We give a simple explicit hitting set generator for read-once branching programs of width $w$ and length...
By Julien Baste, Ignasi Sau, and Dimitrios M. ThilikosSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1623-1648, January 2020. For a finite collection of graphs ${\cal F}$, the $\mathcal{F}$-M-Deletion problem consists in, given a graph...
Livermore, CA, United States
By Wouter Cames van Batenburg, Gwenaël Joret, and Arthur UlmerSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1609-1619, January 2020. A classic theorem of Erdös and Pósa [Canad. J. Math., 17 (1965), pp. 347--352] states that...
By Boris Bukh and Oleksandr RudenkoSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1620-1622, January 2020. Let $a_1,\ldots,a_n$ be a permutation of $[n]$. Two disjoint order-isomorphic subsequences are called twins. We show...
By Hailong Dao, Joseph Doolittle, and Justin LyleSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1602-1608, January 2020. We define and study the notion of a minimal Cohen--Macaulay simplicial complex. We prove that any...
By Parinya Chalermsook, Marek Cygan, Guy Kortsarz, Bundit Laekhanukit, Pasin Manurangsi, Danupon Nanongkai, and Luca TrevisanSIAM Journal on Computing, Volume 49, Issue 4, Page 772-810, January 2020. We consider questions that arise from the intersection between the areas of polynomial-time approximation algorithms, subexponential-time algorithms,...
By Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Fahad Panolan, Saket Saurabh, and Meirav ZehaviSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1587-1601, January 2020. An undirected graph $G$ is $d$-degenerate if every subgraph of $G$ has a vertex of degree...
By Abigail RazSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1559-1586, January 2020. This paper examines bounds on upper tails for cycle counts in $G_{n,p}$. For a fixed graph...
By Talya Eden, Dana Ron, and C. SeshadhriSIAM Journal on Computing, Volume 49, Issue 4, Page 747-771, January 2020. We study the problem of approximating the number of $k$-cliques in a graph when given query access...
By Michael LampisSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1538-1558, January 2020. We revisit the complexity of the classical $k$-Coloring problem parameterized by clique-width. This is a very...
By David G. HarrisSIAM Journal on Computing, Volume 49, Issue 4, Page 711-746, January 2020. We describe approximation algorithms in Linial's classic LOCAL model of distributed computing to find maximum-weight matchings in...
By Tara Fife, Dillon Mayhew, James Oxley, and Charles SempleSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1522-1537, January 2020. A connected matroid $M$ is unbreakable if, for each of its flats $F$, the matroid $M/F$...
By Chong Shangguan and Itzhak TamoSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1493-1504, January 2020. For fixed integers $r\ge 3,e\ge 3,v\ge r+1$, an $r$-uniform hypergraph is called $\mathscr{G}_r(v,e)$-free if the union...
By Pasin Manurangsi and Warut SuksompongSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1505-1521, January 2020. We consider a fair division setting in which $m$ indivisible items are to be allocated among...
By Matthew Jenssen, Peter Keevash, and Will PerkinsSIAM Journal on Computing, Volume 49, Issue 4, Page 681-710, January 2020. We give a fully polynomial-time approximation scheme (FPTAS) and an efficient sampling algorithm for the high-fugacity hard-core...
By Hui Zhu, Liying Kang, Zhenyu Ni, and Erfang ShanSIAM Journal on Discrete Mathematics, Volume 34, Issue 3, Page 1485-1492, January 2020. For a graph $G=(V,E)$, a hypergraph $H$ is called a Berge-$G$ if there is a bijection...
By Scott AaronsonSIAM Journal on Computing, Ahead of Print. We introduce the problem of shadow tomography: given an unknown $D$-dimensional quantum mixed state $\rho$, as well as known two-outcome measurements $E_{1},\ldots,E_{M}$,...
By Ivailo Hartarsky and Tamás Róbert MezeiSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1444-1459, January 2020. Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models...
By Sungjin Im and Benjamin MoseleySIAM Journal on Computing, Volume 49, Issue 3, Page 658-680, January 2020. This paper considers minimizing the $\ell_k$-norms of flow time on a single machine offline using a preemptive...
By Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, and Stéphan ThomasséSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1472-1483, January 2020. A hole in a graph is an induced cycle of length at least 4, and an...
By Sebastián Bustamante, Jan Corsten, Nóra Frankl, Alexey Pokrovskiy, and Jozef SkokanSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1460-1471, January 2020. Confirming a conjecture of Gyárfás, we prove that, for all natural numbers $k$ and $r$, the...
By Karthekeyan Chandrasekaran, Matthias Mnich, and Sahand MozaffariSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1385-1408, January 2020. We investigate the odd multiway node (edge) cut problem where the input is a graph with...
By Alexander Birx and Yann DisserSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1409-1443, January 2020. The online Dial-a-Ride problem is a fundamental online problem in a metric space, where transportation requests...
By Seyyed Aliasghar Hosseini, Fiachra Knox, and Bojan MoharSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1375-1384, January 2020. The game of Cops and Robbers is a well-known game played on graphs. In this paper,...
By Debsoumya Chakraborti and Po-Shen LohSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1354-1374, January 2020. We systematically study a natural problem in extremal graph theory, to minimize the number of edges...
By Chandra Chekuri, Kent Quanrud, and Chao XuSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1334-1353, January 2020. Karger used spanning tree packings [D. R. Karger, J. ACM, 47 (2000), pp. 46--76] to derive...
By Dan Feldman, Melanie Schmidt, and Christian SohlerSIAM Journal on Computing, Volume 49, Issue 3, Page 601-657, January 2020. We develop and analyze a method to reduce the size of a very large set of data...
By Danila Cherkashin and Fedor PetrovSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1326-1333, January 2020. Let $m(n,r)$ denote the minimal number of edges in an $n$-uniform hypergraph which is not $r$-colorable....
By Jun Gao and Jie MaSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1290-1301, January 2020. Answering a question of Häggkvist and Scott, Verstraëte proved that every sufficiently large graph with average...
By Neil J. Y. Fan, Peter L. Guo, Simon C. Y. Peng, and Sophie C. C. SunSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1281-1289, January 2020. We confirm a conjecture of Monical, Tokcan, and Yong on a characterization of the lattice points...
By Akanksha Agrawal, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, and Prafullkumar TaleSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1302-1325, January 2020. A graph $G$ is contractible to a graph $H$ if there is a set $X \subseteq...
By Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing WangSIAM 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 Timothy M. Chan, Sariel Har-Peled, and Mitchell JonesSIAM Journal on Computing, Volume 49, Issue 3, Page 583-600, January 2020. For any constant $d$ and parameter $\varepsilon \in (0,1/2]$, we show the existence of (roughly) $1/\varepsilon^d$ orderings...
By Christian Haase, Florian Kohl, and Akiyoshi TsuchiyaSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1261-1280, January 2020. Since Stanley's [Discrete Comput. Geom., 1 (1986), pp. 9--23] introduction of order polytopes, their geometry has...
By Pavel EtingofSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1248-1260, January 2020. The goal of this paper is to give a systematic method of constructing zero-free regions for...
By Paul Beame, Shayan Oveis Gharan, and Xin YangSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1232-1247, January 2020. We study the bias of random bounded-degree polynomials over odd prime fields and show that, with...
By Paul Dütting, Michal Feldman, Thomas Kesselheim, and Brendan LucierSIAM Journal on Computing, Volume 49, Issue 3, Page 540-582, January 2020. We present a general framework for stochastic online maximization problems with combinatorial feasibility constraints. The framework establishes...
By Sean DewarSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1205-1231, January 2020. We prove that a graph has an infinitesimally rigid placement in a non-Euclidean normed plane if...
By Yezhou Wu and Dong YeSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1192-1204, January 2020. Let $G$ be a graph with edge set $E(G)$ and vertex set $V(G)$, and let $T$...
By Michael Joswig and Georg LohoSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1172-1191, January 2020. We present an algorithm to compute all $n$ nondominated points of a multicriteria discrete optimization problem...
By Yi-Jun Chang, Wenzheng Li, and Seth PettieSIAM Journal on Computing, Volume 49, Issue 3, Page 497-539, January 2020. Vertex coloring is one of the classic symmetry breaking problems studied in distributed computing. In this paper,...
By R. Gabrys, H. S. Dau, C. J. Colbourn, and O. MilenkovicSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1148-1171, January 2020. We address the new problem of designing large families of subsets of a common labeled ground...
By Zeev Dvir, Sivakanth Gopi, Yuzhou Gu, and Avi WigdersonSIAM Journal on Computing, Volume 49, Issue 3, Page 465-496, January 2020. We introduce a simple logical inference structure we call a “spanoid" (generalizing the notion of a...
By Alexandre Blanché, Konrad K. Dabrowski, Matthew Johnson, Vadim V. Lozin, Daniël Paulusma, and Viktor ZamaraevSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1107-1147, January 2020. Clique-width is an important graph parameter due to its algorithmic and structural properties. A graph class...
By Jacob Fox, Tim Roughgarden, C. Seshadhri, Fan Wei, and Nicole WeinSIAM Journal on Computing, Volume 49, Issue 2, Page 448-464, January 2020. We propose a new distribution-free model of social networks. Our definitions are motivated by one of the...
By Rémy Belmonte, Michael Lampis, and Valia MitsouSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1084-1106, January 2020. In Defective Coloring we are given a graph $G=(V,E)$ and two integers ${\chi_d},\Delta^*$ and are asked...
By Bhaswar B. Bhattacharya and Shirshendu GangulySIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1069-1083, January 2020. The upper tail problem for the largest eigenvalue of the Erdös--Rényi random graph $\mathcal{G}_{n,p}$ is to...
By Shi LiSIAM Journal on Computing, Ahead of Print. We study approximation algorithms for problems of scheduling precedence constrained jobs with the objective of minimizing total weighted completion time, in identical...
By Arnold Filtser and Shay SolomonSIAM Journal on Computing, Volume 49, Issue 2, Page 429-447, January 2020. The greedy spanner is arguably the simplest and most well-studied spanner construction. Experimental results demonstrate that it...
By Benjamin Plaut and Tim RoughgardenSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1039-1068, January 2020. The goal of fair division is to distribute resources among competing players in a “fair" way....
By Toufik Mansour, Reza Rastegar, and Alexander RoitershteinSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1011-1038, January 2020. The main theme of this paper is the enumeration of the order-isomorphic occurrence of a pattern...
By Nicholas J. A. Harvey and Jan VondrákSIAM Journal on Computing, Volume 49, Issue 2, Page 394-428, January 2020. The Lovász local lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on...
By Rajko Nenadov and Yanitsa PehovaSIAM Journal on Discrete Mathematics, Volume 34, Issue 2, Page 1001-1010, January 2020. A seminal result of Hajnal and Szemerédi states that if a graph $G$ with $n$ vertices...
By Zihan Tan and Liwei ZengSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 1000-1000, January 2020. This note is an erratum for the paper On the Inequalities of Projected Volumes and the...
By Uriel Feige, Anne Kenyon, and Shimon KoganSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 950-971, January 2020. Let $G$ be a 2-coloring of a complete graph on $n$ vertices, for sufficiently large $n$....
By O-joung Kwon and Sang-il OumSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 972-999, January 2020. For a class $\mathcal C$ of graphs $G$ equipped with functions $f_G$ defined on subsets...
By Ken YamamotoSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 938-949, January 2020. The Horton--Strahler analysis is a graph-theoretic method to measure the bifurcation complexity of branching patterns, by...
By Libor Barto and Michael PinskerSIAM Journal on Computing, Volume 49, Issue 2, Page 365-393, January 2020. The tractability conjecture for finite domain constraint satisfaction problems (CSPs) stated that such CSPs are solvable...
By Rajesh H. Chitnis, Andreas E. Feldmann, MohammadTaghi HajiAghayi, and Daniel MarxSIAM Journal on Computing, Volume 49, Issue 2, Page 318-364, January 2020. Given a vertex-weighted directed graph $G=(V,E)$ and a set $T=\{t_1, t_2, \ldots, t_k\}$ of $k$ terminals, the...
By Alantha NewmanSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 865-884, January 2020. Mömke and Svensson presented a beautiful new approach for the traveling salesman problem on a graph...
By Ran Gelles, Rafail Ostrovsky, and Alan RoytmanSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 904-937, January 2020. We consider the task of communicating an (infinite) data stream in the sliding window model, where...
By Noga Alon, Jonathan D. Cohen, Thomas L Griffiths, Pasin Manurangsi, Daniel Reichman, Igor Shinkar, Tal Wagner, and Alexander YuSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 885-903, January 2020. We consider the problem of determining the maximal $\alpha \in (0,1]$ such that every matching $M$...
By Khaled Elbassioni and Kazuhisa MakinoSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 843-864, January 2020. We give an incremental polynomial time algorithm for enumerating the vertices of any polyhedron $P=P(A,\b1)=\{x\in \mathbb{R}^n...
By Yeow Meng Chee, Duc Tu Dao, Han Mao Kiah, San Ling, and Hengjia WeiSIAM Journal on Computing, Volume 49, Issue 2, Page 284-317, January 2020. A robust positioning pattern is a large array that allows a mobile device to locate its position...
By Antonio Blanca, Andreas Galanis, Leslie Ann Goldberg, Daniel Štefankovič, Eric Vigoda, and Kuan YangSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 742-793, January 2020. We consider the problem of sampling from the Potts model on random regular graphs. It is...
By Silvia Butti and Stanislav ŽivnýSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 825-842, January 2020. A cut $\varepsilon$-sparsifier of a weighted graph $G$ is a reweighted subgraph of $G$ of (quasi)linear...
By Bhaswar B. Bhattacharya, Somabha Mukherjee, and Sumit MukherjeeSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 794-824, January 2020. What is the chance that among a group of $n$ friends, there are $s$ friends all...
By Christian Engels, Mohit Garg, Kazuhisa Makino, and Anup RaoSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 730-741, January 2020. If $k
By Kasper Green Larsen, Omri Weinstein, and Huacheng YuSIAM Journal on Computing, Ahead of Print. This paper proves the first superlogarithmic lower bounds on the cell probe complexity of dynamic Boolean (also known as decision) data structure...
By Boris Bukh and Raymond HogensonSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 721-729, January 2020. Given two random finite sequences from $[k]^n$ such that a prefix of the first sequence is...
By Daniel Irving BernsteinSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 701-720, January 2020. Given a dissimilarity map $\delta$ on a finite set $X$, the set of ultrametrics (equidistant tree...
By F. Becker, P. Montealegre, I. Rapaport, and I. TodincaSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 682-700, January 2020. The broadcast congested clique model (BClique) is a message-passing model of distributed computation where $n$ nodes...
By David Durfee, John Peebles, Richard Peng, and Anup B. RaoSIAM Journal on Computing, Ahead of Print. We show that variants of spectral sparsification routines can preserve the total spanning tree counts of graphs. By Kirchhoff's matrix-tree theorem, this...
By Iyad Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van LeeuwenSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 640-681, January 2020. A fundamental graph problem is to recognize whether the vertex set of a graph $G$ can...
By Anne Broadbent, Zhengfeng Ji, Fang Song, and John WatrousSIAM Journal on Computing, Volume 49, Issue 2, Page 245-283, January 2020. Prior work has established that all problems in NP admit classical zero-knowledge proof systems, and under reasonable...
By Cody D. Murray and R. Ryan WilliamsSIAM Journal on Computing, Ahead of Print. We prove that if every problem in ${NP}$ has $n^k$-size circuits for a fixed constant $k$, then for every ${NP}$-verifier and every...
By Xin Fang, Ghislain Fourier, Jan-Philipp Litza, and Christoph PegelSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 611-639, January 2020. For any marked poset we define a continuous family of polytopes, parametrized by a hypercube, generalizing...
By Kevin G. Milans and Michael C. WigalSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 586-596, January 2020. First-Fit is a greedy algorithm for partitioning the elements of a poset into chains. Let...
By Junpei Nakashima, Yukiko Yamauchi, Shuji Kijima, and Masafumi YamashitaSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 571-585, January 2020. A set function $f$ on a finite set $V$ is submodular if $f(X) + f(Y) \geq...
By Peter J. Dukes and Daniel HorsleySIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 597-610, January 2020. We prove that, for sufficiently large $n$, every graph of order $n$ with minimum degree at...
By Tao Jiang and Yu QiuSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 556-570, January 2020. Given a graph $H$, the Turán number $\mathrm{ex}(n,H)$ is the largest number of edges in an...
By Vera Traub and Jens VygenSIAM 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 Benjamin Plaut and Tim RoughgardenSIAM Journal on Computing, Volume 49, Issue 1, Page 206-243, January 2020. We initiate the study of the communication complexity of fair division with indivisible goods. We focus on...
By Zdeněk Dvořák and Xiaolan HuSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 538-555, January 2020. A graph $G$ is $(a:b)$-colorable if there exists an assignment of $b$-element subsets of $\{1,\ldots,a\}$ to...
By Venkatesan Guruswami and Sai SandeepSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 520-537, January 2020. A $k$-uniform hypergraph is said to be $r$-rainbow colorable if there is an $r$-coloring of its...
By Martin Grohe, Daniel Neuen, and Pascal SchweitzerSIAM 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 Marcel K. de Carli Silva and Levent TunçelSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 470-496, January 2020. Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that...
By Daniel W. Cranston and Jiaao LiSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 497-519, January 2020. For integers $a\ge 2b>0$, a circular $a/b$-flow is a flow that takes values from $\{\pm b,...
By Maria Chudnovsky, Jan Goedgebeur, Oliver Schaudt, and Mingxian ZhongSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 431-469, January 2020. A graph is $H$-free if it has no induced subgraph isomorphic to $H$. We characterize all...
By Stasys Jukna and Hannes SeiwertSIAM Journal on Computing, Volume 49, Issue 1, Page 170-205, January 2020. We prove the first, even superpolynomial, lower bounds on the size of tropical (min,+) and (max,+) circuits...
By Rasmus Kyng and Peng ZhangSIAM Journal on Computing, Ahead of Print. We show that if the nearly linear time solvers for Laplacian matrices and their generalizations can be extended to solve just slightly...
By Mark Braverman, Gil Cohen, and Sumegha GargSIAM Journal on Computing, Ahead of Print. Nisan [Combinatorica, 12 (1992), pp. 449--461] constructed a pseudorandom generator for length $n$, width $n$ read-once branching programs (ROBPs) with error $\varepsilon$...
By Emanuele ViolaSIAM Journal on Computing, Volume 49, Issue 1, Page 119-137, January 2020. We show that for every small AC$^{0}$ circuit $C:\{0,1\}^{\ell}\to\{0,1\}^{m}$ there exists a multiset $S$ of $2^{m-m^{\Omega(1)}}$ restrictions...
By Jesús A. De Loera, Jamie Haddock, and Luis RademacherSIAM Journal on Computing, Volume 49, Issue 1, Page 138-169, January 2020. The complexity of Philip Wolfe's method for the minimum Euclidean-norm point problem over a convex polytope has...
By David Conlon, Jacob Fox, and Benny SudakovSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 385-398, January 2020. A celebrated result of Mantel shows that every graph on n vertices with $\lfloor n^2/4 \rfloor...
By Laure MarêchéSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 370-384, January 2020. We study the set of possible configurations for a general kinetically constrained model (KCM), a nonmonotone...
By Joshua ErdeSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 415-430, January 2020. Many of the tools developed for the theory of tree-decompositions of graphs do not work for...
By Dániel Gerbner, Abhishek Methuku, Gholamreza Omidi, and Máté VizerSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 351-369, January 2020. For a graph G, a hypergraph $\mathcal{H}$ is a Berge copy of G (or a Berge-G...
By Brant JonesSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 399-414, January 2020. The game of best choice (also known as the secretary problem) is a model for sequential...
By Christoph Berkholz and Jakob NordströmSIAM Journal on Computing, Volume 49, Issue 1, Page 98-118, January 2020. We show that there are CNF formulas which can be refuted in resolution in both small space...
By Ran Gu, Jiaao Li, and Yongtang ShiSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 271-307, January 2020. The anti-Ramsey problem was introduced by Erdös, Simonovits, and Sós in 1970s. The anti-Ramsey number of...
By Marcin WrochnaSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 328-350, January 2020. For a fixed graph H, we consider the H-Recoloring problem: given a graph G and two...
By Alexander Barvinok and Anthony Della PellaSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 308-327, January 2020. For a set S of vertices of a graph G, we define its density 0 łeq...
By Uriel Feige, Michal Feldman, and Inbal Talgam-CohenSIAM Journal on Computing, Volume 49, Issue 1, Page 67-97, January 2020. Set functions with convenient properties (such as submodularity) appear in application areas of current interest, such as...
By Samir Khuller, Manish Purohit, and Kanthi K. SarpatwarSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 251-270, January 2020. We study partial and budgeted versions of the well-studied connected dominating set problem. In the...
By Huijia Lin, Rafael Pass, and Pratik SoniSIAM Journal on Computing, Ahead of Print. Non-malleable commitments are a fundamental cryptographic tool for preventing (concurrent) man-in-the-middle attacks. Since their invention by Dolev, Dwork, and Naor in 1991,...
By Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank StephanSIAM 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 Dániel Garamvölgyi and Tibor JordánSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 212-229, January 2020. A $d$-dimensional bar-and-joint framework $(G,p)$, where $G$ is a graph and $p$ maps the vertices of...
By Antonios Antoniadis, Sungjin Im, Ravishankar Krishnaswamy, Benjamin Moseley, Viswanath Nagarajan, Kirk Pruhs, and Clifford SteinSIAM Journal on Computing, Volume 49, Issue 1, Page 37-66, January 2020. We consider virtual circuit routing protocols with an objective of minimizing energy in a network of components...
By Anurag Bishnoi and Valentina PepeSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 230-240, January 2020. A famous conjecture of Ryser states that every $r$-partite hypergraph has vertex cover number ...
By Robert LukoťkaSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 188-211, January 2020. A cycle cover of a graph is a collection of cycles such that each edge of...
By Oliver JanzerSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 241-250, January 2020. For a graph $F$, the $k$-subdivision of $F$, denoted $F^k$, is the graph obtained by replacing...
By Gramoz Goranci, Monika Henzinger, and Pan PengSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 130-162, January 2020. Graph sparsification aims at compressing large graphs into smaller ones while preserving important characteristics of the...
By Sara Fish, Cosmin Pohoata, and Adam ShefferSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 177-187, January 2020. The local properties problem of Erd\Hos and Shelah generalizes many Ramsey problems and some distinct distances...
By Tony Huynh and Peter NelsonSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 163-176, January 2020. We prove that for every proper minor-closed class $\mathcal{M}$ of $\mathbb{F}_p$-representable matroids, there exists an $O(1)$-competitive...
By František KardošSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 62-100, January 2020. Fullerene graphs, i.e., 3-connected planar cubic graphs with pentagonal and hexagonal faces, are conjectured to be...
By Monika Henzinger, Satish Rao, and Di WangSIAM Journal on Computing, Volume 49, Issue 1, Page 1-36, January 2020. We study the problem of computing a minimum cut in a simple, undirected graph and give a...
By Robert Krauthgamer and Havana Inbal RikaSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 101-129, January 2020. We study the following version of cut sparsification. Given a large edge-weighted network $G$ with $k$...
By Michaĺ Deͅbski, Jarosław Grytczuk, Barbara Nayar, Urszula Pastwa, Joanna Sokół, Michał Tuczyński, Przemysław Wenus, and Krzysztof WeͅsekSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 40-52, January 2020. We study colorings of Euclidean spaces avoiding specified patterns on straight lines. This extends the seminal...
By Stefan Felsner, Linda Kleist, Torsten Mütze, and Leon SeringSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 1-39, January 2020. The flip graph of triangulations has as vertices all triangulations of a convex $n$-gon and an...
By Alan M. Frieze and Tomasz TkoczSIAM Journal on Discrete Mathematics, Volume 34, Issue 1, Page 53-61, January 2020. We study the component structure of the random graph $G=G_{n,m,d}$. Here $d=O(1)$ and $G$ is sampled...
By Avraham Ben-Aroya, Dean Doron, and Amnon Ta-ShmaSIAM 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 Rishab Goyal, Venkata Koppula, and Brent WatersSIAM Journal on Computing, Ahead of Print. In this work we provide a traitor tracing construction with ciphertexts that grow polynomially in $\log(n)$, where $n$ is the number of...
By Jin-Yi Cai and Zhiguo FuSIAM 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 Artur Czumaj, Jakub Ła̧cki, Aleksander Ma̧dry, Slobodan Mitrović, Krzysztof Onak, and Piotr SankowskiSIAM Journal on Computing, Ahead of Print. For over a decade now we have been witnessing the success of massive parallel computation frameworks, such as MapReduce, Hadoop, Dryad,...
By Danny Nguyen and Igor PakSIAM 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 László Kozma and Thatchaphol SaranurakSIAM Journal on Computing, Ahead of Print. We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of...
By Elaine Levey and Thomas RothvossSIAM Journal on Computing, Ahead of Print. In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and the goal is to find...
By Yang Cai, Nikhil R. Devanur, and S. Matthew WeinbergSIAM Journal on Computing, Ahead of Print. We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions of Cai, Daskalakis, and Weinberg...
By Stephen Fenner, Rohit Gurjar, and Thomas ThieraufSIAM Journal on Computing, Ahead of Print. We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$,...
By Omer Reingold, Guy N. Rothblum, and Ron D. RothblumSIAM Journal on Computing, Ahead of Print. The celebrated ${\sf IP}={\sf PSPACE}$ theorem [Lund, Fortnow, Karloff, and Nisan, J. ACM, 39 (1992), pp. 859--868; Shamir, J. ACM, 39 (1992),...
By Anat Ganor, Gillat Kol, and Ran RazSIAM Journal on Computing, Ahead of Print. We show an exponential gap between communication complexity and external information complexity by analyzing a communication task suggested as a candidate by...
By Nikhil Bansal, Aravind Srinivasan, and Ola SvenssonSIAM Journal on Computing, Ahead of Print. We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our...
By Sepehr Assadi, Sanjeev Khanna, and Yang LiSIAM Journal on Computing, Ahead of Print. We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover...
By Mark Bun and Justin ThalerSIAM Journal on Computing, Ahead of Print. The approximate degree of a Boolean function $f \colon \{-1, 1\}^n \rightarrow \{-1, 1\}$ is the least degree of a real polynomial...
By Sara Ahmadian, Ashkan Norouzi-Fard, Ola Svensson, and Justin WardSIAM Journal on Computing, Ahead of Print. Clustering is a classic topic in optimization with $k$-means being one of the most fundamental such problems. In the absence of any...
By Brett Hemenway, Noga Ron-Zewi, and Mary WoottersSIAM Journal on Computing, Ahead of Print. We show that the tensor product of a high-rate globally list recoverable code is (approximately) locally list recoverable. List recovery has been...
By Adam Bouland, Lijie Chen, Dhiraj Holden, Justin Thaler, and Prashant Nalini VasudevanSIAM Journal on Computing, Ahead of Print. We examine the power of statistical zero knowledge proofs (captured by the complexity class $SZK$) and their variants. First, we give the...
By Monika Henzinger, Sebastian Krinninger, and Danupon NanongkaiSIAM Journal on Computing, Ahead of Print. 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 networks (the \sf CONGEST model);...
By Leqi ZhuSIAM Journal on Computing, Ahead of Print. In the consensus problem, there are $n$ processes that each has a private input value. Each nonfaulty process must output a single...
By Shaddin Dughmi and Haifeng XuSIAM Journal on Computing, Ahead of Print. Persuasion, defined as the act of exploiting an informational advantage in order to influence the decisions of others, is ubiquitous. Indeed, persuasive...
By Shahar DobzinskiSIAM Journal on Computing, Ahead of Print. We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial auctions with submodular bidders. Dobzinski,...
By Gil CohenSIAM Journal on Computing, Ahead of Print. In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $(2+o(1))\log{n}$-Ramsey graphs on $n$ vertices. Matching Erdös's result...
Aarhus, , Denmark
NY, United States
Coralville, IA, United States
Corvallis, OR, United States
BILBAO, , Spain
Lemont, IL, United States
Blacksburg Area, VA, United States
New York, NY, United States
Philadelphia, PA, United States
Kobe, , Japan
Baltimore, MD, United States
526714, Singapore, Singapore
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.
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.
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.
This joint prize was established in 2002 to honor Sonia Kovalevsky and her work on the theory of differential equations. It is awarded to anyone in the scientific or engineering community whose work highlights the achievements of women in applied and computational mathematics. Nominations can be submitted via the AWM website.
The 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.
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 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.
Through the generosity and inspiration of Gerald and Judith Porter, the Mathematical Association of America (MAA), American Mathematical Society (AMS), and SIAM offer this annual lecture at the Joint Mathematics Meetings. The lecture, first awarded in 2010, is given on a mathematical topic accessible to the broader community.
Named in honor of I. E. Block, a co-founder and the first managing director of SIAM, this lecture is open to the public at the SIAM Annual Meeting. It is intended to encourage public appreciation of applied mathematics and computational science by reaching out to the local community.
Established in 1959, the prize honors John von Neumann, a founder of modern computing. The prize is awarded annually for distinguished contributions to applied mathematics and for the effective communication of these ideas to the community.
The JPBM Communications Award is given annually to reward and encourage communicators who, on a sustained basis, bring mathematical ideas and information to non-mathematical audiences. The prize may be awarded in two categories: For Public Outreach and For Expository and Popular Books. Nominations can be submitted via the AMS website.
~*Learn More*~
The 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 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.
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.
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.
SIAM Journal on Computing (SICOMP) aims to provide coverage of the most significant work going on in the mathematical and formal aspects of computer science and nonnumerical computing. Submissions must be clearly written and make a significant technical contribution.
Looking for financial support to further your research? Fellowships often provide funding plus experiential learning opportunities to young researchers. Learn more about fellowship opportunities.
Read More
Internships allow you to network and forge connections for future job possibilities, while also exploring possible areas of interest. Look at this list of companies who offer valuable opportunities.
Our community is founded on igniting groundbreaking developments in applied math and computational science. Take a deeper dive into your area of study with one of these opportunities.