PA, United States
By Minglong Qin and Penghui YaoSIAM Journal on Computing, Volume 50, Issue 6, Page 1800-1891, January 2021. This paper considers a special class of nonlocal games $(G,\psi)$, where $G$ is a two-player one-round game,...
MA, United Kingdom
NJ, United States
Tallahassee, FL, United States
Bilbao, , Spain
Taiwan
Pittsburgh, PA, United States
Harrisonburg, VA, United States
By Miriam BackensSIAM Journal on Computing, Volume 50, Issue 6, Page 1739-1799, January 2021. Holant problems are a family of counting problems parameterized by sets of algebraic-complex-valued constraint functions and defined...
By Nathan Benedetto Proença, Marcel K. de Carli Silva, and Gabriel CoutinhoSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2880-2907, January 2021. The notion of duality is a key element in understanding the interplay between the stability and...
By Bin Han, Jianxi Mao, and Jiang ZengSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2858-2879, January 2021. We consider a sequence of four variable polynomials by refining Stieltjes's continued fraction for...
By Mika Göös and Aviad RubinsteinSIAM Journal on Computing, Ahead of Print. We prove an $N^{2-o(1)}$ lower bound on the randomized communication complexity of finding an $\epsilon$-approximate Nash equilibrium (for constant $\epsilon>0$) in a...
By Andreas Galanis, Leslie Ann Goldberg, Heng Guo, and Kuan YangSIAM Journal on Computing, Volume 50, Issue 6, Page 1701-1738, January 2021. We give the first efficient algorithm to approximately count the number of solutions in the random $k$-SAT...
By Gabriel Ferreira Barros, Bruno Pasqualotto Cavalar, Yoshiharu Kohayakawa, and Tássio NaiaSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2844-2857, January 2021. If $G$ is a graph and $\vec H$ is an oriented graph, we write $G\to \vec...
Morganton, NC, United States
Princeton, NJ, United States
By Aaron Bernstein and Danupon NanongkaiSIAM Journal on Computing, Ahead of Print. In the distributed all-pairs shortest paths problem, every node in the weighted undirected distributed network (the CONGEST model) needs to know the...
By François Pirot and Jean-Sébastien SereniSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2815-2843, January 2021. We introduce a new method for computing bounds on the independence number and fractional chromatic number...
By Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary WoottersSIAM Journal on Computing, Ahead of Print. We show that Gallager's ensemble of low-density parity-check (LDPC) codes achieves list-decoding capacity with high probability. These are the first graph-based codes...
By Josh Alman and Virginia Vassilevska WilliamsSIAM Journal on Computing, Ahead of Print. We study the known techniques for designing Matrix Multiplication algorithms. The two main approaches are the Laser method of Strassen, and the...
By Nima Anari and Alireza RezaeiSIAM Journal on Computing, Ahead of Print. We prove that the permanent of nonnegative matrices can be deterministically approximated within a factor of $\sqrt{2}^n$ in polynomial time, improving upon...
By Jacob Focke, Leslie Ann Goldberg, Marc Roth, and Stanislav ŽivnýSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2749-2814, January 2021. We study the problem of computing the parity of the number of homomorphisms from an input...
By Joshua Brakensiek and Venkatesan GuruswamiSIAM Journal on Computing, Volume 50, Issue 6, Page 1663-1700, January 2021. A classic result due to Schaefer [Proceedings of STOC 78, ACM, 1978, pp. 216--226] classifies all constraint...
By Dennis Clemens, Fabian Hamann, Yannick Mogge, and Olaf ParczykSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2723-2748, January 2021. Maker-Breaker games are played on a hypergraph $(X,\mathcal{F})$, where $\mathcal{F} \subseteq 2^X$ denotes the family of...
By Logan Crew and Sophie SpirklSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2647-2661, January 2021. In the vector space of symmetric functions, the elements of the basis of elementary symmetric functions...
By Tzvi Alon and Nir HalmanSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2679-2722, January 2021. In this paper we go one step further in the automatic generation of FPTASes for multistage...
By Kristóf Bérczi, Naonori Kakimura, and Yusuke KobayashiSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2662-2678, January 2021. In this paper, we study the problem of maximizing social welfare in combinatorial markets through pricing...
By Jisu Jeong, Eun Jung Kim, and Sang-il OumSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2544-2617, January 2021. Given $n$ subspaces of a finite-dimensional vector space over a fixed finite field ${\mathbb F}$, we...
By Clément Dallard, Martin Milanič, and Kenny ŠtorgelSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2618-2646, January 2021. Treewidth is an important graph invariant, relevant for both structural and algorithmic reasons. A necessary condition...
By Hong-Jian Lai and Lucian MazzaSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2535-2543, January 2021. Abelian group colorings were first introduced by Jaeger et al. in [J. Combin. Theory Ser. B,...
By Mina Dalirrooyfard, Thuy Duong Vuong, and Virginia Vassilevska WilliamsSIAM Journal on Computing, Volume 50, Issue 5, Page 1627-1662, January 2021. We consider the pattern detection problem in graphs: given a constant size pattern graph $H$ and a...
By Artur Czumaj, Peter Davies, and Merav ParterSIAM Journal on Computing, Volume 50, Issue 5, Page 1603-1626, January 2021. We settle the complexity of the $(\Delta+1)$-coloring and $(\Delta+1)$-list coloring problems in the \sf CONGESTED CLIQUE model...
By René SittersSIAM Journal on Computing, Volume 50, Issue 5, Page 1580-1602, January 2021. We give a polynomial time approximation scheme for the weighted traveling repairman problem (TRP) in the Euclidean...
By Momoko HayamizuSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2490-2516, January 2021. Attempting to recognize a tree inside a phylogenetic network is a fundamental undertaking in evolutionary analysis....
By Nathan Bowler, Joshua Erde, Florian Lehner, and Max PitzSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2459-2489, January 2021. It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded...
By Dani Kotlar, Elad Roda, and Ran ZivSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2517-2519, January 2021. We show that given two bases $A$ and $B$ of a matroid $\mathcal M$ and any...
By Xiaofeng Gu, Wei Meng, Martin Rolek, Yue Wang, and Gexin YuSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2520-2534, January 2021. The 2-dimensional global rigidity has been shown to be equivalent to 3-connectedness and redundant rigidity by...
By Bart M. P. Jansen, Marcin L. Pilipczuk, and Erik Jan van LeeuwenSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2387-2429, January 2021. We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted...
By Oliver Cooley, Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolás Sanhueza-Matamala, and Julian ZallaSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2430-2458, January 2021. Given integers $k,j$ with $1\le j \le k-1$, we consider the length of the longest $j$-tight...
By Vera Traub, Jens Vygen, and Rico ZenklusenSIAM Journal on Computing, Ahead of Print. We present a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP)....
By Maria Chudnovsky, Jason King, Michał Pilipczuk, Paweł Rzaͅżewski, and Sophie SpirklSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2357-2386, January 2021. We study the Max Partial $H$-Coloring problem: given a graph $G$, find the largest induced subgraph...
By S. Thomas McCormick, Britta Peis, Robert Scheidweiler, and Frank VallentinSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2345-2356, January 2021. In this note we give a polynomial time algorithm for solving the closest vector problem...
By Bernard Lidický and Florian PfenderSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2328-2344, January 2021. Finding exact Ramsey numbers is a problem typically restricted to relatively small graphs. The flag algebra...
By Jun Gao, Qingyi Huo, and Jie MaSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2317-2327, January 2021. Resolving a conjecture of Bollobás and Erdös, Gyárfás proved that every graph $G$ of chromatic number...
By Vipul Goyal, Silas Richelson, Alon Rosen, and Margarita ValdSIAM Journal on Computing, Volume 50, Issue 5, Page 1537-1579, January 2021. In their seminal work on nonmalleable cryptography, Dolev, Dwork, and Naor showed how to construct a nonmalleable...
By Oliver Weller-Davies, Mike Steel, and Jotun HeinSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2304-2316, January 2021. Polymer models are a widely used tool to study the prebiotic formation of metabolism at the...
By Ron Aharoni, Joseph Briggs, Ron Holzman, and Zilin JiangSIAM Journal on Discrete Mathematics, Volume 35, Issue 4, Page 2293-2303, January 2021. We prove that every family of (not necessarily distinct) odd cycles $O_1, \dots, O_{2\lceil n/2 \rceil-1}$...
By Alireza Farhadi, MohammadTaghi Hajiaghayi, Kasper Green Larsen, and Elaine ShiSIAM Journal on Computing, Ahead of Print. Sorting extremely large datasets is a frequently occurring task in practice. These datasets are usually much larger than the computer's main memory;...
By Felix Hommelsheim, Moritz Muehlenthaler, and Oliver SchaudtSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2265-2292, January 2021. Suppose we are given a bipartite graph that admits a perfect matching and an adversary may...
By Weiting Cao, Douglas B. West, and Yan YangSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2234-2248, January 2021. A $t$-bar visibility representation of a graph assigns each vertex up to $t$ horizontal bars in...
By David Conlon and Mykhaylo TyomkynSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2249-2264, January 2021. For a fixed graph $H$, what is the smallest number of colors $C$ such that there...
By Edita Máčajová and Martin ŠkovieraSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2223-2233, January 2021. The well-known shortest cycle cover conjecture suggests that every bridgeless graph $G$ can have its edges...
By Luiz MoreiraSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2210-2222, January 2021. We say that a graph $G$ is Ramsey for $H_1$ versus $H_2$ and write $G \to...
By Gilad Asharov, Moni Naor, Gil Segev, and Ido ShahafSIAM Journal on Computing, Volume 50, Issue 5, Page 1501-1536, January 2021. Searchable symmetric encryption (SSE) enables a client to store a database on an untrusted server while supporting...
By Patrick Bennett, Ryan Cushman, and Andrzej DudekSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2145-2169, January 2021. A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $\tau(G)$ is at most...
By Kristóf Bérczi, Tamás Schwarcz, and Yutaro YamaguchiSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2192-2209, January 2021. In the list coloring problem for two matroids, we are given matroids $M_1=(S,{\mathcal{I}}_1)$ and $M_2=(S,{\mathcal{I}}_2)$ on...
By Shang-En Huang and Seth PettieSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2129-2144, January 2021. We prove better lower bounds on additive spanners and emulators, which are lossy compression schemes for...
By Sam Spiro and Jacques VerstraëteSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2170-2191, January 2021. For two graphs $F$ and $H$, the relative Turán number ${ex}(H,F)$ is the maximum number of...
By Guozhen Rong, Wenjun Li, Jianxin Wang, and Yongjie YangSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2115-2128, January 2021. In 1990, Hendry conjectured that all Hamiltonian chordal graphs are cycle extendable. After a series of...
By Enric Boix-Adserà, Matthew Brennan, and Guy BreslerSIAM Journal on Computing, Ahead of Print. We consider the problem of counting $k$-cliques in $s$-uniform Erdös--Rényi hypergraphs $G(n,c,s)$ with edge density $c$ and show that its fine-grained average-case...
By Linus SetiabrataSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2093-2114, January 2021. For every directed acyclic graph $G$, we characterize the faces of the root polytope $\tilde Q_G...
By Srikanth Srinivasan, Utkarsh Tripathi, and S. VenkiteshSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2070-2092, January 2021. The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$...
By Eric N. StuckySIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2049-2069, January 2021. We discuss two surprising properties of a family of polynomials that generalize the Mahonian $q$-Catalan polynomials...
By Hans L. Bodlaender, Sudeshna Kolay, and Astrid PieterseSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2003-2038, January 2021. Given a graph $G$, a $q$-open neighborhood conflict-free coloring or $q$-ONCF-coloring is a vertex coloring $c\colon...
By Thomas Magnard, Michael Skotnica, and Martin TancerSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1978-2002, January 2021. We say that a pure simplicial complex ${\mathbf K}$ of dimension $d$ satisfies the removal-collapsibility condition...
By Qing Cui and On-Hei Solomon LoSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 2039-2048, January 2021. For any positive integer $k$, define $f(k)$ (respectively, $f_3(k)$) to be the minimal integer $\ge k$...
By Nutan Limaye, Karteek Sreenivasaiah, Srikanth Srinivasan, Utkarsh Tripathi, and S. VenkiteshSIAM Journal on Computing, Volume 50, Issue 4, Page 1461-1499, January 2021. In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform ${\mathrm{AC}}^0[\oplus]$. In particular, we show...
By Radoslav Fulek and Balázs KeszeghSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1964-1977, January 2021. A 0-1 matrix $M$ is saturating for a 0-1 matrix $P$ if $M$ does not contain...
By Papa A. SissokhoSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1952-1963, January 2021. Let $a_1,\ldots,a_n$ and $b_1,\ldots,b_m$ be fixed positive integers, and let ${\mathcal S}$ denote the set of...
By Johannes Bausch and Felix LeditzkySIAM Journal on Computing, Volume 50, Issue 4, Page 1410-1460, January 2021. The error threshold of a one-parameter family of quantum channels is defined as the largest noise level...
By Manuel Bodirsky, Florent Madelaine, and Antoine MottetSIAM Journal on Computing, Volume 50, Issue 4, Page 1359-1409, January 2021. The logic MMSNP is a restricted fragment of existential second-order logic which can express many interesting queries...
By Alexander A. Sherstov and Pei WuSIAM Journal on Computing, Ahead of Print. The threshold degree of a Boolean function $f\colon{{\{0,1\}}^n}\to{\{0,1\}}$ is the minimum degree of a real polynomial $p$ that represents $f$ in sign:...
By Lucas de Oliveira Contiero, Carlos Hoppen, Hanno Lefmann, and Knut OdermannSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1927-1951, January 2021. The Fano plane is the unique linear 3-uniform hypergraph on seven vertices and seven hyperedges. It...
By Michael Anastos, Alan Frieze, and Pu GaoSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1854-1880, January 2021. We study the Hamiltonicity of the following model of a random graph. Suppose that we partition...
By Frank Fuhlbrück, Johannes Köbler, and Oleg VerbitskySIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1792-1853, January 2021. As is well known, the isomorphism problem for vertex-colored graphs with color multiplicity at most 3...
By Benjamin Bergougnoux and Mamadou Moustapha KantéSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1881-1926, January 2021. In this paper, we design a framework to obtain efficient algorithms for several problems with a...
By Moïse Blanchard, Jesús A. De Loera, and Quentin LouveauxSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1746-1768, January 2021. Motivated by the problem of bounding the number of iterations of the simplex algorithm, we investigate...
By Daniel W. Cranston and Matthew P. YanceySIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1769-1791, January 2021. For each integer $k\ge 2$, we determine a sharp bound on ${mad}(G)$ such that $V(G)$ can...
By Bhaskar Ray Chaudhury, Telikepalli Kavitha, Kurt Mehlhorn, and Alkmini SgouritsaSIAM Journal on Computing, Volume 50, Issue 4, Page 1336-1358, January 2021. The fair division of indivisible goods is a very well-studied problem. The goal of this problem is...
By Wanshun Yang, Yiqiao Wang, Weifan Wang, and Ko-Wei LihSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1729-1745, January 2021. A 1-planar graph is a graph that can be drawn in the Euclidean plane such that...
By Yi Li, Ruosong Wang, and David P. WoodruffSIAM Journal on Computing, Volume 50, Issue 4, Page 1287-1335, January 2021. In the subspace sketch problem one is given an $n \times d$ matrix $A$ with $O(\log(nd))$ bit...
By Carol T. ZamfirescuSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1706-1728, January 2021. Motivated by a conjecture of Grünbaum and a problem of Katona, Kostochka, Pach, and Stechkin, both...
By Imre Leader, Žarko Ranđelović, and Eero RätySIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1678-1687, January 2021. In this paper we study the following geometric problem: given $2^n-1$ real numbers $x_A$ indexed by...
By Rohit Gurjar and Nisheeth K. VishnoiSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1688-1705, January 2021. We show that for any regular matroid on m elements and $\alpha \geq 1$, the number...
By Marcin KozikSIAM Journal on Computing, Volume 50, Issue 4, Page 1263-1286, January 2021. The characterization of all the constraint satisfaction problems solvable by local consistency checking (also known as...
By James A. Long, Kevin G. Milans, and Andrea MunaroSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1673-1677, January 2021. We show that connected graphs admit sublinear longest path transversals. This improves an earlier result of...
By Shachar LovettSIAM Journal on Computing, Volume 50, Issue 4, Page 1248-1262, January 2021. A $k \times n$ matrix over a field is called an MDS (maximum distance separable) matrix if...
By Mokshay Madiman, Liyao Wang, and Jae Oh WooSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1628-1649, January 2021. Lower bounds for the Rényi entropies of sums of independent random variables taking values in cyclic...
By Jang Soo Kim and Meesue YooSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1650-1672, January 2021. In the literature there are several determinant formulas for Schur functions: the Jacobi--Trudi formula, the dual...
By Travis Dillon and Pablo SoberónSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1615-1627, January 2021. A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a...
By Ke Chen, Adrian Dumitrescu, Wolfgang Mulzer, and Csaba D. TóthSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1592-1614, January 2021. Let $P=(p_1, p_2, \dots, p_n)$ be a polygonal chain in $\mathbb{R}^d$. The stretch factor of $P$...
By Siu-Wing Cheng and Man-Kit LauSIAM Journal on Computing, Volume 50, Issue 4, Page 1200-1247, January 2021. We present self-adjusting data structures for answering point location queries in convex and connected subdivisions. Let...
By Oleg R. MusinSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1578-1591, January 2021. In the present paper, we consider the majorization theorem (also known as Karamata's inequality) and the...
By Elad Aigner-Horev and Dan HefetzSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1569-1577, January 2021. Given an $n$-vertex graph $H$ with minimum degree at least $d n$ for some fixed $d...
By Nima Anari, Kuikui Liu, and Shayan Oveis GharanSIAM Journal on Computing, Ahead of Print. We say a probability distribution $\mu$ is spectrally independent if an associated pairwise influence matrix has a bounded largest eigenvalue for the...
By Charles Carlson, Alexandra Kolla, Ray Li, Nitya Mani, Benny Sudakov, and Luca TrevisanSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1557-1568, January 2021. For a graph $G$, let $f(G)$ denote the size of the maximum cut in $G$. The...
By Jozsef Balogh, Nathan Lemons, and Cory PalmerSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1525-1535, January 2021. Let $\mathcal{H}$ be an $r$-uniform hypergraph. The minimum positive co-degree of $\mathcal{H}$, denoted by $\delta_{r-1}^+(\mathcal{H})$, is...
By Martin VodičkaSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1536-1547, January 2021. The Kimura 3-parameter model is one of the most fundamental phylogenetic models in algebraic statistics. We...
By Tao Zhang and Gennian GeSIAM Journal on Discrete Mathematics, Volume 35, Issue 3, Page 1548-1556, January 2021. For an $r$-graph $G$, the minimum $(r-1)$-degree $\delta(G)$ is the largest integer $t$ such that every...
By Arturs Backurs, Liam Roditty, Gilad Segal, Virginia Vassilevska Williams, and Nicole WeinSIAM Journal on Computing, Volume 50, Issue 4, Page 1155-1199, January 2021. Among the most important graph parameters is the diameter, the largest distance between any two vertices. There...
By Jérémie Dusart, Derek G. Corneil, and Michel HabibSIAM Journal on Computing, Volume 50, Issue 3, Page 1148-1153, January 2021. This corrigendum corrects errors found by Jérémie Dusart in the proof of correctness of the algorithms in...
By Alexandr Andoni, Keren Censor-Hillel, Jing Chen, and Debmalya PanigrahiSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-i-STOC16-iii, January 2021. This issue of SICOMP contains 14 specially selected papers from the 48th Annual ACM Symposium on Theory...
By Martin Dyer, Mark Jerrum, Haiko Müller, and Kristina VuškovićSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1503-1524, January 2021. Jerrum, Sinclair, and Vigoda [J. ACM, 51 (2004), pp. 671--697] showed that the permanent of any...
By John Engbers, Aysel Erey, Jacob Fox, and Xiaoyu HeSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1478-1502, January 2021. Let $P_G(k)$ be the number of proper $k$-colorings of a finite simple graph $G$. Tomescu's conjecture,...
By Safwat Nassar and Raphael YusterSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1460-1477, January 2021. What must one do in order to make acyclic a given oriented graph? Here we look...
By Keren Censor-Hillel and Michal DorySIAM Journal on Computing, Volume 50, Issue 3, Page 1103-1147, January 2021. We address the fundamental network design problem of constructing approximate minimum spanners. Our contributions are for the...
By Tsz Chiu Kwok, Lap Chi Lau, and Akshay RamachandranSIAM Journal on Computing, Volume 50, Issue 3, Page 1034-1102, January 2021. We present a spectral analysis of a continuous scaling algorithm for matrix scaling and operator scaling. The...
By Yoshiharu Kohayakawa, Walner Mendonça, Guilherme Oliveira Mota, and Bjarne SchülkeSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1447-1459, January 2021. We investigate the problem of determining how many monochromatic trees are necessary to cover the vertices...
By Jesse Beisegel, Carolin Denkert, Ekkehard Köhler, Matjaž Krnc, Nevena Pivač, Robert Scheffler, and Martin StrehlerSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1418-1446, January 2021. Graph searches and the corresponding search trees can exhibit important structural properties and are used in...
By Fedor V. Fomin and Petr A. GolovachSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1298-1336, January 2021. A fundamental theorem of Whitney from 1933 asserts that 2-connected graphs $G$ and $H$ are 2-isomorphic,...
By Sándor P. Fekete, Linda Kleist, and Dominik KrupkeSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1337-1355, January 2021. We provide a comprehensive study of a natural graph optimization problem that arises from transition costs...
By Ben Clark, Kevin Grace, James Oxley, and Stefan H. M. van ZwamSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1356-1380, January 2021. Subject to announced results by Geelen, Gerards, and Whittle [Towards a structure theory for matrices and...
By Wenjian Liu and Ning NingSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1381-1417, January 2021. In this paper, we analyze the tree reconstruction problem, which is to determine whether symbols at...
By David Eppstein and Vijay V. VaziraniSIAM Journal on Computing, Volume 50, Issue 3, Page 1014-1033, January 2021. In 1988, Vazirani gave an NC algorithm for computing the number of perfect matchings in $K_{3,3}$-minor-free graphs...
By Srinivasan Arunachalam, Alex Bredariol Grilo, and Aarthi SundaramSIAM Journal on Computing, Volume 50, Issue 3, Page 972-1013, January 2021. In this paper, we study the quantum learnability of constant-depth classical circuits under the uniform distribution and...
By Edita Máčajová and Martin ŠkovieraSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1287-1297, January 2021. The perfect matching index of a cubic graph $G$, denoted by $\pi(G)$, is the smallest...
By Duško Jojić, Gaiane Panina, and Rade ŽivaljevićSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1268-1286, January 2021. We prove several versions of Alon's necklace-splitting theorem, subject to additional constraints, as illustrated by the...
By Stefan Kiefer and Corto N. MascleSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1252-1267, January 2021. Let $n$ be a natural number, and let $\mathcal{M}$ be a set of $n \times n$-matrices...
By Carlos Hoppen, Yoshiharu Kohayakawa, Richard Lang, Hanno Lefmann, and Henrique StagniSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1238-1251, January 2021. Given a family of graphs $\mathcal{F}$, we prove that the normalized edit distance of any given...
By Xiaohui Bei, Shiteng Chen, Ji Guan, Youming Qiao, and Xiaoming SunSIAM Journal on Computing, Volume 50, Issue 3, Page 924-971, January 2021. In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of...
By Louis Esperet, Cyril Gavoille, and Carla GroenlandSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1224-1237, January 2021. A subgraph $H$ of a graph $G$ is isometric if the distances between vertices in $H$...
By Mohamed Barakat, Reimer Behrends, Christopher Jefferson, Lukas Kühne, and Martin LeunerSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1201-1223, January 2021. In this paper we describe a parallel algorithm for generating all nonisomorphic rank 3 simple matroids...
By Alan M. FriezeSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1182-1200, January 2021. We consider the following question. We have a dense regular graph $G$ with degree $\alpha n$,...
By Aleksandrs Belovs and Eric BlaisSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-406-STOC16-433, January 2021. We show that every algorithm for testing $n$-variate Boolean functions for monotonicity must have query complexity $\tilde{\Omega}(n^{1/4})$....
By Debsoumya Chakraborti, Da Qi Chen, and Mihir HasabnisSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1165-1181, January 2021. This paper considers an edge minimization problem in saturated bipartite graphs. An $n$ by $n$ bipartite...
By Zdeněk Dvořák, Rose McCarty, and Sergey NorinSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1149-1164, January 2021. We give a natural sufficient condition for an intersection graph of compact convex sets in $\mathbb{R}^d$...
By Maria Axenovich, Jean-Sébastien Sereni, Richard Snyder, and Lea WeberSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1136-1148, January 2021. We consider a natural, yet seemingly not much studied, extremal problem in bipartite graphs. A bi-hole...
By Amin Coja-Oghlan and Max Hahn-KlimrothSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1096-1135, January 2021. Guided by the theory of graph limits, we investigate a variant of the cut metric for...
By Sébastien Bubeck, Michael B. Cohen, James R. Lee, and Yin Tat LeeSIAM Journal on Computing, Volume 50, Issue 3, Page 909-923, January 2021. We consider metrical task systems on tree metrics and present an $O(\mathrm{depth} \times \log n)$-competitive randomized algorithm...
By Dongchun Han and Hanbin ZhangSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1077-1095, January 2021. In this paper, we present a reciprocity on finite abelian groups involving zero-sum sequences. Let $G$...
By Pravesh K. Kothari, Raghu Meka, and Prasad RaghavendraSIAM Journal on Computing, Ahead of Print. We show that for constraint satisfaction problems (CSPs), weakly exponential size linear programming relaxations are as powerful as the explicit linear program...
By Alan Arroyo, R. Bruce Richter, and Matthew SunoharaSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1050-1076, January 2021. Motivated by the successful application of geometry to proving the Harary--Hill conjecture for “pseudolinear” drawings of...
By Hongliang Lu, Xingxing Yu, and Xiaofan YuanSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1022-1049, January 2021. We prove that, for any integers $k,l$ with $k\ge 3$ and $k/2
By Xiaonan Liu and Xingxing YuSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 1005-1021, January 2021. Whitney proved in 1931 that 4-connected planar triangulations are Hamiltonian. Hakimi, Schmeichel, and Thomassen conjectured...
By Rajko Nenadov and Miloš TrujićSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 988-1004, January 2021. A seminal result by Komlós, Sarközy, and Szemerédi states that if a graph $G$ with $n$...
By Andrea Freschi, Joseph Hyde, Joanna Lada, and Andrew TreglownSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 970-975, January 2021. Balogh, Csaba, Jing, and Pluhár [Electron. J. Combin., 27 (2020)] recently determined the minimum degree threshold...
By Igor E. Shparlinski and Qiang WangSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 976-987, January 2021. We obtain new bounds of exponential sums modulo a prime $p$ with sparse polynomials ...
By Xiaofeng GuSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 948-952, January 2021. The toughness $t(G)$ of a connected graph $G$ is defined as $t(G)=\min\{\frac{|S|}{c(G-S)}\}$, in which the minimum...
By Guillaume DucoffeSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 953-969, January 2021. Given an $n$-vertex $m$-edge graph $G$ with nonnegative edge-weights, a shortest cycle is one minimizing the...
By Wojciech Czerwiński, Wojciech Nadara, and Marcin PilipczukSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 934-947, January 2021. Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in...
By Amit Sahai and Brent WatersSIAM Journal on Computing, Volume 50, Issue 3, Page 857-908, January 2021. We introduce a new technique, that we call punctured programs, to apply indistinguishability obfuscation towards cryptographic problems....
By Bill Jackson, Anthony Nixon, and Shin-ichi TanigawaSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 928-933, January 2021. We consider the problem of characterizing the generic rigidity of bar-joint frameworks in $\mathbb{R}^d$ in which...
By Ruben Becker, Sebastian Forster, Andreas Karrenbauer, and Christoph LenzenSIAM Journal on Computing, Volume 50, Issue 3, Page 815-856, January 2021. We present a method for solving the transshipment problem---also known as uncapacitated minimum cost flow---up to a...
By Gábor Damásdi, Stefan Felsner, António Gira͂o, Balázs Keszegh, David Lewis, Dániel T. Nagy, and Torsten UeckerdtSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 915-927, January 2021. We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite...
By Henning Bruhn, Felix Joos, and Oliver SchaudtSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 893-914, January 2021. In the 1960s, Erdös and Pósa proved that there is a packing-covering duality for cycles in...
By Steven Chaplick, Fedor V. Fomin, Petr A. Golovach, Dušan Knop, and Peter ZemanSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 840-892, January 2021. We obtain new polynomial kernels and compression algorithms for Path Cover and Cycle Cover, the well-known...
By Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan UllmanSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-377-STOC16-405, January 2021. Adaptivity is an important feature of data analysis---the choice of questions to ask about a dataset often...
By Ivan Aidun, Frances Dean, Ralph Morrison, Teresa Yu, and Julie YuanSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 814-839, January 2021. We associate to any graph a sequence of integers called the gonality sequence of the graph,...
By Tom Gur and Oded LachishSIAM Journal on Computing, Volume 50, Issue 2, Page 788-813, January 2021. A locally decodable code (LDC) $C \colon \{0,1\}^k \to \{0,1\}^n$ is an error correcting code wherein individual...
By Pankaj K. Agarwal, Boris Aronov , Esther Ezra , and Joshua ZahlSIAM Journal on Computing, Volume 50, Issue 2, Page 760-787, January 2021. In 2015, Guth proved that if $\EuScript{S}$ is a collection of $n$ $g$-dimensional semialgebraic sets in ${\mathbb{R}}^d$...
By Hoon Oh, Ariel D. Procaccia, and Warut SuksompongSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 788-813, January 2021. We investigate the query complexity of the fair allocation of indivisible goods. For two agents with...
By Chien-Chung Huang, Mathieu Mari, Claire Mathieu, Kevin Schewior, and Jens VygenSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 752-769, January 2021. We devise a constant-factor approximation algorithm for the maximization version of the edge-disjoint paths problem if...
By Magnús M. Halldórsson and Tigran TonoyanSIAM Journal on Computing, Volume 50, Issue 2, Page 718-759, January 2021. An overarching issue in resource management of wireless networks is assessing their capacity: How much communication can...
By Stasys JuknaSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 770-787, January 2021. The problem of constructing hazard-free Boolean circuits (those avoiding electronic glitches) dates back to the 1940s...
By Dawei Huang, Seth Pettie, Yixiang Zhang, and Zhijun ZhangSIAM Journal on Computing, Volume 50, Issue 2, Page 674-717, January 2021. In this paper we explore fundamental problems in randomized communication complexity such as computing SetIntersection on sets...
By Martín D. SafeSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 707-751, January 2021. In 1969, Tucker characterized proper circular-arc graphs as those graphs whose augmented adjacency matrices have the...
By Greg BodwinSIAM Journal on Computing, Volume 50, Issue 2, Page 662-673, January 2021. Given $p$ node pairs in an $n$-node graph, a distance preserver is a sparse subgraph that agrees...
By Haitao Wang and Jingru ZhangSIAM Journal on Computing, Volume 50, Issue 2, Page 602-635, January 2021. We consider a classical $k$-center problem in trees. Let $T$ be a tree of $n$ vertices such...
By Pasin Manurangsi and Warut SuksompongSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 668-706, January 2021. We study a resource allocation setting where $m$ discrete items are to be divided among $n$...
By Rose McCartySIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 661-667, January 2021. We prove that every bipartite graph of sufficiently large average degree has either a $K_{t,t}$-subgraph or...
By Rohit Gurjar, Thomas Thierauf, and Nisheeth K. VishnoiSIAM Journal on Computing, Volume 50, Issue 2, Page 636-661, January 2021. We present a geometric approach toward derandomizing the isolation lemma of Mulmuley, Vazirani, and Vazirani. We...
By Oleg Karpenkov and Christian MuellerSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 637-660, January 2021. In this paper we study a classical Maxwell question on the existence of self-stresses for frameworks,...
By O-joung Kwon and Jean-Florent RaymondSIAM Journal on Discrete Mathematics, Volume 35, Issue 2, Page 597-636, January 2021. A class $\mathcal{F}$ of graphs has the induced Erdös--Pósa property if there exists a function $f$...
By Harold N. Gabow and Piotr SankowskiSIAM Journal on Computing, Volume 50, Issue 2, Page 555-601, January 2021. For an undirected graph or multigraph $G=(V,E)$ and a function $f:V\to \mathbb{Z_+}$, an $f$-factor is a...
By Karolina Okrasa and Paweł RzaͅżewskiSIAM Journal on Computing, Volume 50, Issue 2, Page 487-508, January 2021. For a fixed graph $H$, by Hom($H$) we denote the computational problem which asks whether a given...
By Paweł Gawrychowski, Haim Kaplan, Shay Mozes, Micha Sharir, and Oren WeimannSIAM Journal on Computing, Volume 50, Issue 2, Page 509-554, January 2021. We present an explicit and efficient construction of additively weighted Voronoi diagrams on planar graphs. Let $G$...
By Harold N. Gabow and Piotr SankowskiSIAM Journal on Computing, Volume 50, Issue 2, Page 440-486, January 2021. Let $G=(V,E)$ be a weighted graph or multigraph, with $f$ or $b$ a function assigning a nonnegative...
By Rajesh Jayaram and David WoodruffSIAM Journal on Computing, Volume 50, Issue 2, Page 382-439, January 2021. In this paper, we resolve the one-pass space complexity of perfect $L_p$ sampling for $p \in (0,2)$...
By Pavel Dvořák, Andreas E. Feldmann, Dušan Knop, Tomáš Masařík, Tomáš Toufar, and Pavel VeselýSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 546-574, January 2021. We study the Steiner Tree problem, in which a set of terminal vertices needs to be...
By Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak, and Magnus WahlströmSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 575-596, January 2021. Golovach, Paulusma, and Song [Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized...
By Weiming Feng, Nisheeth K. Vishnoi, and Yitong YinSIAM Journal on Computing, Volume 50, Issue 2, Page 350-381, January 2021. In this paper, we study the problem of sampling from a graphical model when the model...
By M. McDevitt and N. RuškucSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 495-520, January 2021. Algorithmic decidability is established for two order-theoretic properties of downward closed subsets defined by finitely many...
By Marcin Briański, Piotr Micek, Michał Pilipczuk, and Michał T. SewerynSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 447-464, January 2021. We prove that for every nowhere dense class of graphs $\mathcal{C}$, positive integer $d$, and $\varepsilon>0$,...
By Michael Tait and Robert WonSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 521-531, January 2021. An $m$-general set in $AG(n,q)$ is a set of points such that any subset of size...
By Qizhong Lin and Xing PengSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 532-545, January 2021. Let $B_n^{(k)}$ be the book graph which consists of $n$ copies of $K_{k+1}$ all ...
By Eyal Kushilevitz, Rafail Ostrovsky, Emmanuel Prouff, Adi Rosén, Adrian Thillard, and Damien VergnaudSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 465-484, January 2021. We consider multiparty information-theoretic private protocols, and specifically their randomness complexity. The randomness complexity of...
By Ngo Dac TanSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 485-494, January 2021. M. A. Henning and A. Yeo conjectured in [SIAM J. Discrete Math., 26 (2012), pp. 687--694]...
By Henning Bruhn-Fujimoto and Matthias HeinleinSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 392-430, January 2021. We prove that every graph $G$ contains either $k$ edge-disjoint $K_4$-subdivisions or a set $X$ of...
By Runrun Liu, Martin Rolek, D. Christopher Stephens, Dong Ye, and Gexin YuSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 431-446, January 2021. For a given graph $H$, a graph $G$ is H-linked if, for every injection $\varphi: V(H)...
By Miaomiao Han, Jiaao Li, Rong Luo, Yongtang Shi, and Cun-Quan ZhangSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 376-391, January 2021. This paper studies the fundamental relations among integer flows, modulo orientations, integer-valued and real-valued circular...
By Matteo Gallet, Georg Grasegger, Jan Legerský, and Josef SchichoSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 325-361, January 2021. We interpret realizations of a graph on the sphere up to rotations as elements of a...
By Pavol Hell, César Hernández-Cruz, Jing Huang, and Jephian C.-H. LinSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 362-375, January 2021. We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella...
By Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, and Amnon Ta-ShmaSIAM Journal on Computing, Volume 50, Issue 2, Page 301-349, January 2021. We strengthen the notion of double samplers, first introduced by Dinur and Kaufman [``High dimensional expanders imply...
By William M. Hoza and Chris UmansSIAM Journal on Computing, Ahead of Print. Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by...
By Quentin Dubroff, Jacob Fox, and Max Wenqiang XuSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 322-324, January 2021. We present two short proofs giving the best known asymptotic lower bound for the maximum element...
By A. Nicholas Day and Amites SarkarSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 294-306, January 2021. We disprove a conjecture of Nagy on the maximum number of copies $N$($G$, $H$) of a...
By Ilya Shkredov and Jozsef SolymosiSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 307-321, January 2021. In this paper we show examples for applications of the Bombieri--Lang conjecture in additive combinatorics, giving...
By Moran Feldman, Ola Svensson, and Rico ZenklusenSIAM Journal on Computing, Volume 50, Issue 2, Page 255-300, January 2021. We introduce a new rounding technique designed for online optimization problems, which is related to contention resolution...
By Nina Kamcev, Anita Liebenau, David R. Wood, and Liana YepremyanSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 281-293, January 2021. A graph $G$ is Ramsey for a graph $H$ if every 2-coloring of the edges...
By P. Dütting, T. Roughgarden, and I. Talgam-CohenSIAM Journal on Computing, Volume 50, Issue 1, Page 211-254, January 2021. We initiate the study of computing (near-)optimal contracts in succinctly representable principal-agent settings. Here optimality means maximizing...
By Sidhanth Mohanty, Ryan O'Donnell, and Pedro ParedesSIAM Journal on Computing, Ahead of Print. For every constant $d \geq 3$ and $\epsilon > 0$, we give a deterministic $\operatorname{poly}(n)$-time algorithm that outputs a $d$-regular graph on...
By Oliver Cooley, Nemanja Draganić, Mihyun Kang, and Benny SudakovSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 267-280, January 2021. Given a large graph $H$, does the binomial random graph $G(n,p)$ contain a copy of $H$...
By Louis DeBiasio, Allan Lo, Theodore Molla, and Andrew TreglownSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 250-266, January 2021. Let $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph...
By Dustin G. Mixon and Hans ParshallSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 234-249, January 2021. For $d\in\{5,6\}$, we classify arrangements of $d + 2$ points in ${RP}^{d-1}$ for which the minimum...
By Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann PitassiSIAM Journal on Computing, Volume 50, Issue 1, Page 171-210, January 2021. Lifting theorems are theorems that relate the query complexity of a function $f:\{0,1\}^{n}\to \{0,1\}$ to the communication...
By Alexander Garver, Stefan Grosser, Jacob P. Matherne, and Alejandro MoralesSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 205-233, January 2021. We introduce a class of posets, which includes both ribbon posets (skew shapes) and $d$-complete posets,...
By Oliver Roche-NewtonSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 194-204, January 2021. Let $A \subset \mathbb R$ and $G \subset A \times A$. We prove that for any...
By Satoshi Noguchi, Xiao-Nan Lu, Masakazu Jimbo, and Ying MiaoSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 179-193, January 2021. BCH codes are among the best practical cyclic codes widely used in consumer electronics, communication systems,...
By Steffen Borgwardt and Charles VissSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 152-178, January 2021. Clustering is one of the fundamental tasks in data analytics and machine learning. In many situations,...
By Hernán González-Aguilar, David Orden, Pablo Pérez-Lantero, David Rappaport, Carlos Seara, Javier Tejel, and Jorge UrrutiaSIAM Journal on Computing, Volume 50, Issue 1, Page 145-170, January 2021. Let $P$łabelpage1 be a set of $n$ points in the plane. We consider a variation of the...
By Archontia Giannopoulou, Michał Pilipczuk, Jean-Florent Raymond, Dimitrios M. Thilikos, and Marcin WrochnaSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 105-151, January 2021. Suppose ${\mathcal{F}}$ is a finite family of graphs. We consider the following meta-problem, called $\mathcal{F}$-Immersion Deletion:...
By Nir Bitansky, Akshay Degwekar, and Vinod VaikuntanathanSIAM Journal on Computing, Volume 50, Issue 1, Page 98-144, January 2021. Much of modern cryptography, starting from public-key encryption and going beyond, is based on the hardness of...
By Meysam Alishahi and Frédéric MeunierSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 91-104, January 2021. Haviv [European J. Combin., 81 (2019), pp. 84--97] has recently proved that some topological lower...
By Benny Applebaum, Zvika Brakerski, and Rotem TsabarySIAM Journal on Computing, Volume 50, Issue 1, Page 68-97, January 2021. We show that any multiparty functionality can be evaluated using a 2-round protocol with perfect correctness and...
By Jeongwan Haah, Matthew B. Hastings, Robin Kothari, and Guang Hao LowSIAM Journal on Computing, Ahead of Print. We study the problem of simulating the time evolution of a lattice Hamiltonian, where the qubits are laid out on a lattice...
By Satoru Iwata and Yusuke KobayashiSIAM Journal on Computing, Ahead of Print. The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection problems, is so general that...
By Laurent Feuilloley and Michel HabibSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 55-90, January 2021. This paper deals with the characterization and the recognition of graph classes. A popular way to...
By Hélène Barcelo, Curtis Greene, Abdul Salam Jarrah, and Volkmar WelkerSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 35-54, January 2021. We prove that if $G$ is a graph without 3-cycles and 4-cycles, then the discrete cubical...
By Andrea MontanariSIAM Journal on Computing, Ahead of Print. Let ${A}\in{\mathbb R}^{n\times n}$ be a symmetric random matrix with independent and identically distributed (i.i.d.) Gaussian entries above the diagonal. We consider...
By Vincent Cohen-Addad, Éric Colin de Verdière, and Arnaud de MesmaySIAM Journal on Computing, Volume 50, Issue 1, Page 1-31, January 2021. For an undirected edge-weighted graph $G$ and a set $R$ of pairs of vertices called pairs of...
By Benny Applebaum, Barak Arkis, Pavel Raykov, and Prashant Nalini VasudevanSIAM Journal on Computing, Volume 50, Issue 1, Page 32-67, January 2021. In the conditional disclosure of secrets (CDS) problem [Gertner et al., J. Comput. System Sci., 60 (2000),...
By Hiroki OshimaSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 1-22, January 2021. Submodularity is one of the most important properties in combinatorial optimization, and $k$-submodularity is a generalization...
By Qizhong Lin and Xiudi LiuSIAM Journal on Discrete Mathematics, Volume 35, Issue 1, Page 23-34, January 2021. The notion of goodness for Ramsey numbers was introduced by Burr and Erdös in 1983. For...
By Julia Chuzhoy, David H. K. Kim, and Rachit NimavatSIAM Journal on Computing, Ahead of Print. In the classical node-disjoint paths (\sf NDP) problem, the input consists of an undirected $n$-vertex graph $G$, and a collection ${\mathcal M}=\{(s_1,t_1),\ldots,(s_k,t_k)\}$...
By Akash Kumar, C. Seshadhri, and Andrew StolmanSIAM Journal on Computing, Ahead of Print. Let $G$ be an undirected, bounded degree graph with $n$ vertices. Fix a finite graph $H$, and suppose one must remove $\varepsilon...
By Urmila MahadevSIAM Journal on Computing, Ahead of Print. We present the first leveled fully homomorphic encryption scheme for quantum circuits with classical keys. The scheme allows a classical client to...
By Jatin Batra, Naveen Garg, and Amit KumarSIAM Journal on Computing, Ahead of Print. In the weighted flow-time problem on a single machine, we are given a set of $n$ jobs, where each job has a...
By Timothy Chu, Yu Gao, Richard Peng, Sushant Sachdeva, Saurabh Sawlani, and Junxing 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 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 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 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 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 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 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 Elaine Levey and Thomas RothvoSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-201-STOC16-217, January 2021. In a classical problem in scheduling, one has $n$ unit size jobs with a precedence order and...
By Yang Cai, Nikhil R. Devanur, and S. Matthew WeinbergSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-160-STOC16-200, January 2021. We provide a unified view of many recent developments in Bayesian mechanism design, including the black-box reductions...
By Stephen Fenner, Rohit Gurjar, and Thomas ThieraufSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-218-STOC16-235, January 2021. We show that the bipartite perfect matching problem is in quasi-$\mathsf{NC}^2$. That is, it has uniform circuits...
By Omer Reingold, Guy N. Rothblum, and Ron D. RothblumSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-255-STOC16-340, January 2021. The celebrated ${\sf IP}={\sf PSPACE}$ theorem [Lund, Fortnow, Karloff, and Nisan, J. ACM, 39 (1992), pp. 859--868;...
By Anat Ganor, Gillat Kol, and Ran RazSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-236-STOC16-254, January 2021. We show an exponential gap between communication complexity and external information complexity by analyzing a communication task...
By Nikhil Bansal, Aravind Srinivasan, and Ola SvenssonSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-138-STOC16-159, January 2021. We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum...
By Sepehr Assadi, Sanjeev Khanna, and Yang LiSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-341-STOC16-376, January 2021. We resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For...
By Monika Henzinger, Sebastian Krinninger, and Danupon NanongkaiSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-98-STOC16-137, January 2021. We present a deterministic $(1+o(1))$-approximation $(n^{1/2+o(1)}+D^{1+o(1)})$-time algorithm for solving the single-source shortest paths problem on distributed weighted...
By Leqi ZhuSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-18-STOC16-29, January 2021. In the consensus problem, there are $n$ processes that each has a private input value. Each nonfaulty...
By Shaddin Dughmi and Haifeng XuSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-68-STOC16-97, January 2021. Persuasion, defined as the act of exploiting an informational advantage in order to influence the decisions of...
By Shahar DobzinskiSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-1-STOC16-17, January 2021. We study a central problem in algorithmic mechanism design: constructing truthful mechanisms for welfare maximization in combinatorial...
By Gil CohenSIAM Journal on Computing, Volume 50, Issue 3, Page STOC16-30-STOC16-67, January 2021. In his 1947 paper that inaugurated the probabilistic method, Erdös proved the existence of $(2+o(1))\log{n}$-Ramsey graphs on...
Hampton, VA, United States
OH, United States
Arlington, TX, United States
Denver, CO, United States
Sydney, , Australia
Blacksburg, VA, United States
West Lafayette, IN, United States
Dallas, TX, United States
Roskilde, , Denmark
Nanjing, , China
Evanston, IL, United States
Los Angeles, CA, United States
Cambridge, MA, United States
Riverside, CA, United States
Lincoln, NE, United States
Lewiston, ME, United States
MD, United States
Singapore
Salt Lake City, UT, United States
Chicago, IL, United States
Tempe, AZ, United States
Beijing, , China
Philadelphia, PA, United States
Hong Kong
Golden, CO, United States
Pasadena, CA, United States
Shanghai, , China
Waterloo, ON, Canada
Chapel Hill, NC, United States, Chapel Hill, NC, United States
Medford, MA, United States
Baltimore, MD, United States, MD, United States
The SIAM Student Paper Prize is awarded annually to the student author(s) of the most outstanding paper(s) accepted by SIAM journals within the three years preceding the nomination deadline. Starting with the 2018 award, the focus of the prize is to recognize outstanding scholarship by students in SIAM journals.
This prize was created in 2013 to emphasize George Pólya’s legacy of communicating mathematics effectively. It joins two long-standing Pólya prizes SIAM has awarded in combinatorics and other fields beginning in 1969.
Established in 1998 in memory of Ralph E. Kleinman, the prize recognizes contributions that bridge the gap between high-level mathematics and engineering problems. The award is based on the quality and impact of the mathematics.
Established in 2020, the prize is awarded every two years to an early career researcher for recent contributions in the field of applied and computational discrete algorithms.
This joint prize was established in 2002 to honor Sonia Kovalevsky and her work on the theory of differential equations. It is awarded to anyone in the scientific or engineering community whose work highlights the achievements of women in applied and computational mathematics. Nominations can be submitted via the AWM website.
Established in 2007, the prize honors Dénes König, a pioneer of discrete mathematics still influencing the field. It is awarded for outstanding research by an individual in their early career, based on publication in peer-reviewed journals.
This prize is intended to emphasize applications of combinatorics and is funded by the estate of Stella Pólya in memory of her husband George. The prize is a modification of the older George Pólya Prize in Combinatorics, originally established as the George Pólya Prize in 1969.
The prize was established in 1986 in memory of Richard C. DiPrima, who served SIAM for many years and in 1979–1980 as SIAM President. It aims to recognize an early career researcher in applied mathematics and is based on the doctoral dissertation.
The Pioneer Prize is awarded every four years at the International Council for Industrial and Applied Mathematics (ICIAM) Congress to one individual for pioneering work introducing applied mathematical methods and scientific computing techniques to an industrial problem area or a new scientific field of applications. Nominations can be submitted via the ICIAM website.
Through the generosity and inspiration of Gerald and Judith Porter, the Mathematical Association of America (MAA), American Mathematical Society (AMS), and SIAM offer this annual lecture at the Joint Mathematics Meetings. The lecture, first awarded in 2010, is given on a mathematical topic accessible to the broader community.
Named in honor of I. E. Block, a co-founder and the first managing director of SIAM, this lecture is open to the public at the SIAM Annual Meeting. It is intended to encourage public appreciation of applied mathematics and computational science by reaching out to the local community.
Established in 1959, the prize honors John von Neumann, a founder of modern computing. The prize is awarded annually for distinguished contributions to applied mathematics and for the effective communication of these ideas to the community.
The JPBM Communications Award is given annually to reward and encourage communicators who, on a sustained basis, bring mathematical ideas and information to non-mathematical audiences. The prize may be awarded in two categories: For Public Outreach and For Expository and Popular Books. Nominations can be submitted via the AMS website.
~*Learn More*~
Established in 1967, the prize honors Norbert Wiener, a founder of the field of cybernetics. The prize is awarded every three years by SIAM and the American Mathematical Society (AMS) for an outstanding contribution to applied mathematics. Nominations can be submitted via the AMS website.
The prize recognizes students for outstanding solutions to real world math problems. It is awarded to six of the teams judged "Outstanding" in the Mathematical Contest in Modeling (MCM) administered annually by the Consortium for Mathematics and Its Applications (COMAP). Registration is accepted via the COMAP website.
The SIAM Outstanding Paper Prize is not currently active. For the 20 years before it was discontinued in 2019, the SIAM Outstanding Paper Prizes brought attention to papers published in SIAM journals. Three awards were made each year to the authors of papers deemed by SIAM journal editors-in-chief worthy of particular attention.
The prize, established in 1985 and originally intended to be awarded periodically, is now awarded annually for contributions to the advancement of applied mathematics on the national or international level.
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.