FORT COLLINS, CO, United States
By Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, and Mihalis YannakakisSIAM Journal on Computing, Volume 51, Issue 3, Page 492-548, June 2022. We study the optimal lottery problem and the optimal mechanism design problem in the setting of a...
By Piotr Indyk and Tal WagnerSIAM Journal on Computing, Volume 51, Issue 3, Page 467-491, June 2022. We study the problem of representing all distances between $n$ points in ${\mathbb R}^d$, with arbitrarily small...
Hampton, VA, United States
Hong Kong
By Arturo Merino, Ondřej Mička, and Torsten MützeSIAM Journal on Computing, Volume 51, Issue 3, Page 379-423, June 2022. The well-known middle levels conjecture asserts that for every integer $n\geq 1$, all binary strings of length...
By Paweł M. Idziak and Jacek KrzaczkowskiSIAM Journal on Computing, Volume 51, Issue 3, Page 337-378, June 2022. The satisfiability of Boolean circuits is NP-complete in general but becomes polynomial time when restricted either to...
By Péter Pál Pach and Richárd PalinczaSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1135-1142, June 2022. We show that sets avoiding six-term arithmetic progressions in $\mathbb{Z}_6^n$ have size at most $5.709^n$. It...
By Gilad Asharov, Wei-Kai Lin, and Elaine ShiSIAM Journal on Computing, Volume 51, Issue 3, Page 424-466, June 2022. We consider the classical problem of sorting an input array containing $n$ elements, where each element is...
By Huacheng YuSIAM Journal on Computing, Ahead of Print. For positive integers $U$, $n$, and $\sigma$, given a set $S$ of $n$ (distinct) keys from key space $[U]$, each associated with...
By Lijie Chen and Hanlin RenSIAM Journal on Computing, Ahead of Print. In a recent breakthrough, [C. Murray and R. R. Williams, STOC 2018, ACM, New York, 2018, pp. 890--901] proved that ${NQP}...
By Yin Tat Lee and Santosh VempalaSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-400-STOC17-488, April 2022. We introduce the geodesic walk for sampling Riemannian manifolds and apply it to the problem of generating...
By Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio OkamotoSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1102-1123, June 2022. Motivated by adjacency in perfect matching polytopes, we study the shortest reconfiguration problem of perfect matchings...
By Andy Drucker, Ravi Kumar, Amit Sahai, and Mohit SinghSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-i-STOC17-ii, April 2022. This issue of SICOMP contains ten specially selected papers from STOC 2017, the Forty-ninth Annual ACM Symposium...
By Ewan Davies and Freddie IllingworthSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1124-1134, June 2022. In 1967, Erdös asked for the greatest chromatic number, $f(n)$, amongst all $n$-vertex, triangle-free graphs. An...
By Tongseok Lim and Robert J. McCannSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1093-1101, June 2022. In this paper, we explicitly estimate the number of points in a subset $A \subset...
Phildelphia, PA, United States
By Daniel Lokshtanov, Saket Saurabh, and Vaishali SurianarayananSIAM Journal on Computing, Ahead of Print. In the Min $k$-Cut problem, the input consists of an edge weighted graph $G$ and an integer $k$, and the task is...
Albuquerque, NM, United States
By Anup Rao and Amir YehudayoffSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1071-1092, June 2022. We prove anticoncentration bounds for the inner product of two independent random vectors and use these...
By Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, and Noam SolomonSIAM Journal on Computing, Volume 51, Issue 2, Page 315-335, April 2022. A hitting-set generator (HSG) is a polynomial map ${{\mathsf{Gen}}}:{\mathbb{F}}^k \to {\mathbb{F}}^n$ such that for all $n$-variate polynomials...
By Candida Bowtell and Joseph HydeSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1038-1063, June 2022. The study of asymptotic minimum degree thresholds that force matchings and tilings in hypergraphs is a...
By Ahmad Abdi, Gérard Cornuéjols, Bertrand Guenin, and Levent TunçelSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1012-1037, June 2022. A vector is dyadic if each of its entries is a dyadic rational number, i.e., an...
By Igor E. ShparlinskiSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1064-1070, June 2022. We obtain upper bounds on the cardinality of Hilbert cubes in finite fields, which avoid large...
By Tarun Kathuria, Yang P. Liu, and Aaron SidfordSIAM Journal on Computing, Ahead of Print. We present an algorithm which given any $m$-edge directed graph with positive integer capacities at most $U$, vertices $a$ and $b$, and...
By Thomas Kahle, Dinh Van Le, and Tim RömerSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 975-999, June 2022. We relate finite generation of cones, monoids, and ideals in increasing chains (the local situation) to...
By Guorong Gao, An Chang, and Yuan HouSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 1000-1011, June 2022. An $r$-uniform hypergraph is linear if every two edges intersect in at most one vertex. Let...
By Grigory Ivanov and Márton NaszódiSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 951-957, June 2022. We introduce a new variant of quantitative Helly-type theorems: the minimal homothetic distance of the intersection...
By Esther Ezra, Orit E. Raz, Micha Sharir, and Joshua ZahlSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 958-974, June 2022. We show that the maximum number of pairwise nonoverlapping $k$-rich lenses (lenses formed by at least...
By Marc Roth, Johannes Schmitt, and Philip WellnitzSIAM Journal on Computing, Ahead of Print. Given a graph property $\Phi$, the problem $\#\ensuremath{{\sc IndSub}}(\Phi)$ asks, on input of a graph $G$ and a positive integer $k$, to...
By Stijn Cambie, Wouter Cames van Batenburg, Rémi de Joannis de Verclos, and Ross J. KangSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 939-950, June 2022. We wish to bring attention to a natural but slightly hidden problem, posed by Erdös and...
By Ittai Abraham, Arnold Filtser, Anupam Gupta, and Ofer NeimanSIAM Journal on Computing, Volume 51, Issue 2, Page 290-314, April 2022. We study the problem of embedding shortest-path metrics of weighted graphs into $\ell_p$ spaces. We introduce...
By Akanksha Agrawal, Lawqueen Kanesh, Fahad Panolan, M. S. Ramanujan, and Saket SaurabhSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 911-921, June 2022. In the literature on parameterized graph problems, there has been an increased effort in recent years...
By Dániel Marx, Marcin Pilipczuk, and Michal PilipczukSIAM Journal on Computing, Volume 51, Issue 2, Page 254-289, April 2022. There are numerous examples of the so-called “square root phenomenon” in the field of parameterized algorithms: many...
By Karl DäubelSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 867-887, June 2022. The ring loading problem emerged in the 1990s to model an important special case of telecommunication...
By Tomáš Masařík, Marcin Pilipczuk, Paweł Rzaͅżewski, and Manuel SorgeSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 922-938, June 2022. The Directed Grid Theorem, stating that there is a function $f$ such that a directed graph...
By Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, and S. Matthew WeinbergSIAM Journal on Computing, Ahead of Print. We provide the first separation in the approximation guarantee achievable by truthful and nontruthful algorithms for combinatorial auctions with polynomial communication. Specifically,...
By Jeff Erickson, Ivor van der Hoog, and Tillmann MiltzowSIAM Journal on Computing, Ahead of Print. We study algorithmic problems that belong to the complexity class of the existential theory of the reals ($\exists \mathbb{R}$). A problem is...
By M. Levent Doğan, Alperen A. Ergür, Jake D. Mundo, and Elias TsigaridasSIAM Journal on Discrete Mathematics, Volume 36, Issue 2, Page 888-910, June 2022. Motivated by applications in combinatorial geometry, we consider the following question: Let $\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_m)$ be an...
By Nicolas Bitar, Eric Goles, and Pedro MontealegreSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 823-866, March 2022. Diffusion-limited aggregation (DLA) is a cluster-growth model that consists of a set of particles that are...
By Hung Le and Shay SolomonSIAM Journal on Computing, Ahead of Print. Euclidean spanners are important geometric structures, having found numerous applications over the years. Cornerstone results in this area from the late 1980s...
By Zilong Yan and Yuejian PengSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 786-822, March 2022. The Turán number of an $r$-uniform graph $F$, denoted by $ex(n,F)$, is the maximum number of...
By Jérémy Lavollée and Konrad J. SwanepoelSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 777-785, March 2022. A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth conjectured in 1981 that...
By Carol T. ZamfirescuSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 755-776, March 2022. Motivated by work of Haythorpe, Thomassen and the author showed that there exists a positive constant...
By Mohammad Bavarian, Thomas Vidick, and Henry YuenSIAM Journal on Computing, Volume 51, Issue 2, Page 214-253, April 2022. We introduce a simple transformation on two-player nonlocal games, called “anchoring,” and prove an exponential-decay parallel repetition...
By Kenjiro TakazawaSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 702-727, March 2022. We propose a framework for optimal $t$-matchings excluding prescribed $t$-factors in bipartite graphs. The proposed framework...
By Yahav Alon and Michael KrivelevichSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 728-754, March 2022. Consider the random subgraph process on a base graph $G$ on $n$ vertices: a sequence $\lbrace...
By Konstantin Makarychev, Yury Makarychev, and Ilya RazenshteynSIAM Journal on Computing, Ahead of Print. Consider an instance of Euclidean $k$-means or $k$-medians clustering. We show that the cost of the optimal solution is preserved up to...
By Alexander Golovnev, Gleb Posobin, Oded Regev, and Omri WeinsteinSIAM Journal on Computing, Ahead of Print. Proving superlogarithmic data structure lower bounds in the static group model has been a fundamental challenge in computational geometry since the early...
By Caitlyn Booms-Peot, Daniel Erman, and Jay YangSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 682-701, March 2022. When do syzygies depend on the characteristic of the field? Even for well-studied families of examples,...
By Sushmita Gupta, Saket Saurabh, and Meirav ZehaviSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 596-681, March 2022. Stable Marriage is a fundamental problem to both computer science and economics. Four well-known NP-hard optimization...
By Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, and Michael PinskerSIAM Journal on Computing, Volume 51, Issue 2, Page 175-213, April 2022. We produce a class of $\omega$-categorical structures with finite signature by applying a model-theoretic construction---a refinement of...
By Josh Alman and Lijie ChenSIAM Journal on Computing, Ahead of Print. For a matrix $H$ over a field $\mathbb{F}$, its rank-$r$ rigidity, denoted by $\mathscr{R}_{H}(r)$, is the minimum Hamming distance from $H$ to...
By Jørgen Bang-Jensen, Thomas Schweser, and Michael StiebitzSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 578-595, March 2022. Let $D$ be a digraph, let $p \geq 1$ be an integer, and let $f: V(D)...
By Paul Balister, Emil Powierski, Alex Scott, and Jane TanSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 573-577, March 2022. Let $\mathcal F$ be an antichain of finite subsets of $\mathbb N$. How quickly can...
By Aris Filos-Ratsikas and Paul W. GoldbergSIAM Journal on Computing, Ahead of Print. We resolve the computational complexity of three problems known as Necklace Splitting, Consensus-Halving, and Discrete Ham sandwich, showing that they are PPA-complete....
By Victor Chepoi, Kolja Knauer, and Manon PhilibertSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 509-535, March 2022. This paper considers completions of tope graphs of complexes of oriented matroids (COMs) to ample partial...
By Pavel Dvořák, Dušan Knop, and Tomáš ToufarSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 536-572, March 2022. In this paper, we study the Target Set Selection problem from a parameterized complexity perspective. Here...
By Guillermo Pineda-Villavicencio and Benjamin SchröterSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 490-508, March 2022. We specify what is meant for a polytope to be reconstructible from its graph or dual...
By Gianira N. Alfarano, Martino Borello, Alessandro Neri, and Alberto RavagnaniSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 461-489, March 2022. We develop three approaches of combinatorial flavor to study the structure of minimal codes and cutting...
By Hongyi Jiang and Amitabh BasuSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 449-460, March 2022. We show that one can enumerate the vertices of the convex hull of integer points in...
By Barnabás JanzerSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 436-448, March 2022. Given an edge-colored graph, we say that a subgraph is rainbow if all of its edges...
By Mamadou M. Kanté, Christophe Paul, and Dimitrios M. ThilikosSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 411-435, March 2022. The graph parameter of pathwidth can be seen as a measure of the topological resemblance...
By Chien-Chung Huang, Naonori Kakimura, Simon Mauras, and Yuichi YoshidaSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 355-382, March 2022. Maximizing a monotone submodular function under various constraints is a classical and intensively studied problem. However,...
By Marta Panizzut and Magnus Dehli VigelandSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 383-410, March 2022. Given a tropical line $L$ and a smooth tropical surface $X$, we look at the position...
By Magnus Bordewich, Simone Linz, Megan Owen, Katherine St. John, Charles Semple, and Kristina WickeSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 336-354, March 2022. We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary...
By Vsevolod F. LevSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 315-335, March 2022. We determine the structure of a finite subset $A$ of an abelian group given that $|2A|<3(1-\varepsilon)|A|,\...
By David J. AldousSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 299-314, March 2022. The size of the largest common subtree (maximum agreement subtree) of two independent uniform random binary...
By Nir Bitansky, Dakshita Khurana, and Omer PanethSIAM Journal on Computing, Ahead of Print. The round complexity of zero-knowledge protocols is a long-standing open question and is yet to be settled under standard assumptions. So far,...
By Sandra Kiefer and Daniel NeuenSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 252-298, March 2022. The Weisfeiler--Leman procedure is a widely used technique for graph isomorphism testing that works by iteratively...
By Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan VenkitasubramaniamSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-333-STOC17-399, April 2022. Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally...
By Zequn Lv, Mei Lu, and Yi ZhangSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 241-251, March 2022. Let $r\ge k\ge 2$ and $K_{r,n}^{(k)}$ denote the complete $n$-balanced $r$-partite $k$-uniform hypergraph, whose vertex...
By Martin Balko and Máté VizerSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 214-228, March 2022. For an integer $k \geq 2$, an ordered $k$-uniform hypergraph $\mathcal{H}=(H,<)$ is a $k$-uniform hypergraph $H$...
By Zichao Dong and Zhuo WuSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 229-240, March 2022. Let $G$ be a graph on $n$ vertices of independence number $\alpha(G)$ such that every induced...
By Ágnes Cseh, Yuri Faenza, Telikepalli Kavitha, and Vladlena PowersSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 188-213, March 2022. An instance of the marriage problem is given by a graph $G = (A \cup B,E)$,...
By Pedro Araújo, Simón Piga, and Mathias SchachtSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 147-169, March 2022. We study sufficient conditions for the existence of Hamilton cycles in uniformly dense 3-uniform hypergraphs. Problems...
By Alex Scott, Paul Seymour, and Sophie SpirklSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 170-187, March 2022. A pure pair in a graph $G$ is a pair $(Z_1,Z_2)$ of disjoint sets of vertices...
By Georgios Amanatidis and Pieter KleerSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 118-146, March 2022. The switch Markov chain has been extensively studied as the most natural Markov chain Monte Carlo...
By Siddharth Bhandari and Sayantan ChakrabortySIAM Journal on Computing, Ahead of Print. We present a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k...
By Michał Lasoń and Mateusz MichałekSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 114-117, March 2022. We prove that seminormality of cut polytopes is equivalent to normality.
By Ajani De Vas Gunasekara and Daniel HorsleySIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 47-63, March 2022. For positive integers $n$ and $k$ with $n \geq k$, an $(n,k,1)$-design is a pair $(V,...
By Manuel Lafond, Binhai Zhu, and Peng ZouSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 64-91, March 2022. In computational biology, tandem duplication is an important biological phenomenon which can occur either at the...
By Anthony Harrison, Jenya Soprunova, and Patrick TierneySIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 92-102, March 2022. The lattice size $\operatorname{ls_\Delta}(P)$ of a lattice polygon $P$ with respect to the standard simplex...
By Nikolaos Fountoulakis, Felix Joos, and Guillem PerarnauSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 1-46, March 2022. We consider bond percolation on random graphs with given degrees and bounded average degree. In particular,...
By Jiaxi Nie and Jacques VerstraëteSIAM Journal on Discrete Mathematics, Volume 36, Issue 1, Page 103-113, March 2022. In this paper, we consider an extension of cycle-complete graph Ramsey numbers to Berge cycles in...
By Aaron Bernstein, Maximilian Probst Gutenberg, and Christian Wulff-NilsenSIAM Journal on Computing, Ahead of Print. Computing the strongly connected Components (SCCs) in a graph $G=(V,E)$ is known to take only $O(m + n)$ time using an algorithm...
By Mika Göös and Aviad 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 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 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 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 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 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 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 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 Pravesh K. Kothari, Raghu Meka, and Prasad RaghavendraSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-305-STOC17-332, April 2022. We show that for constraint satisfaction problems (CSPs), weakly exponential size linear programming relaxations are as powerful...
By William M. Hoza and Chris UmansSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-281-STOC17-304, April 2022. Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to...
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 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, Volume 51, Issue 2, Page STOC17-238-STOC17-280, April 2022. The matroid parity (or matroid matching) problem, introduced as a common generalization of matching and matroid intersection...
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 Julia Chuzhoy, David H. K. Kim, and Rachit NimavatSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-189-STOC17-237, April 2022. In the classical node-disjoint paths (\sf NDP) problem, the input consists of an undirected $n$-vertex graph $G$,...
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, Volume 51, Issue 2, Page STOC17-152-STOC17-188, April 2022. It is shown that the parity game can be solved in quasi-polynomial time. The parameterized parity game---with...
By Avraham Ben-Aroya, Dean Doron, and Amnon Ta-ShmaSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-31-STOC17-49, April 2022. The breakthrough result of Chattopadhyay and Zuckerman [Explicit two-source extractors and resilient functions, in Proceedings of the...
By Jin-Yi Cai and Zhiguo FuSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-50-STOC17-151, April 2022. We prove a complexity classification theorem that classifies all counting constraint satisfaction problems (\#CSP) over Boolean variables...
By Danny Nguyen and Igor PakSIAM Journal on Computing, Volume 51, Issue 2, Page STOC17-1-STOC17-30, April 2022. We study the computational complexity of short sentences in Presburger arithmetic (Short-PA). Here by “short” we mean...
Phoenix, AZ, United States
Philadelphia, PA, United States
TX, United States
Kennesaw, GA, United States
North Wales, PA, United States
Kenilworth, NJ, United States
Livermore, CA, United States
Baltimore, MD, United States
Berkeley, CA, United States, Berkeley, CA, United States
Berkeley, CA, United States
Smithfield, RI, United States
Tacoma, WA, United States
Aarhus, , Denmark
Tempe, AZ, United States
Seattle, WA, United States
Charlottesville, VA, United States
Santa Clara, CA, United States
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.
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.
Established in 2007, the prize honors Dénes König, a pioneer of discrete mathematics still influencing the field. It is awarded for outstanding research by an individual in their early career, based on publication in peer-reviewed journals.
This prize is intended to emphasize applications of combinatorics and is funded by the estate of Stella Pólya in memory of her husband George. The prize is a modification of the older George Pólya Prize in Combinatorics, originally established as the George Pólya Prize in 1969.
The prize was established in 1986 in memory of Richard C. DiPrima, who served SIAM for many years and in 1979–1980 as SIAM President. It aims to recognize an early career researcher in applied mathematics and is based on the doctoral dissertation.
Established in 1967, the prize honors Norbert Wiener, a founder of the field of cybernetics. The prize is awarded every three years by SIAM and the American Mathematical Society (AMS) for an outstanding contribution to applied mathematics. Nominations can be submitted via the AMS website.
The Pioneer Prize is awarded every four years at the International Council for Industrial and Applied Mathematics (ICIAM) Congress to one individual for pioneering work introducing applied mathematical methods and scientific computing techniques to an industrial problem area or a new scientific field of applications. Nominations can be submitted via the ICIAM website.
Through the generosity and inspiration of Gerald and Judith Porter, the Mathematical Association of America (MAA), American Mathematical Society (AMS), and SIAM offer this annual lecture at the Joint Mathematics Meetings. The lecture, first awarded in 2010, is given on a mathematical topic accessible to the broader community.
Named in honor of I. E. Block, a co-founder and the first managing director of SIAM, this lecture is open to the public at the SIAM Annual Meeting. It is intended to encourage public appreciation of applied mathematics and computational science by reaching out to the local community.
Established in 1959, the prize honors John von Neumann, a founder of modern computing. The prize is awarded annually for distinguished contributions to applied mathematics and for the effective communication of these ideas to the community.
The JPBM Communications Award is given annually to reward and encourage communicators who, on a sustained basis, bring mathematical ideas and information to non-mathematical audiences. The prize may be awarded in two categories: For Public Outreach and For Expository and Popular Books. Nominations can be submitted via the AMS website.
~*Learn More*~
The MAA-SIAM-AMS Hrabowski-Gates-Tapia-McBay (HGTM) Lecture is named after four influential scientists of color: Freeman Hrabowski, President of the University of Maryland at Baltimore County; James S. Gates, University of Maryland, College Park; Richard Tapia, Rice University; and Shirley McBay, Founder and former President of Quality Education for Minorities. This lecture started in 2016 as an activity of the Mathematical Association of America’s Committee on Minority Participation and became a jointly sponsored MAA-SIAM-AMS event in 2018.
The prize recognizes students for outstanding solutions to real world math problems. It is awarded to six of the teams judged "Outstanding" in the Mathematical Contest in Modeling (MCM) administered annually by the Consortium for Mathematics and Its Applications (COMAP). Registration is accepted via the COMAP website.
The SIAM Outstanding Paper Prize is not currently active. For the 20 years before it was discontinued in 2019, the SIAM Outstanding Paper Prizes brought attention to papers published in SIAM journals. Three awards were made each year to the authors of papers deemed by SIAM journal editors-in-chief worthy of particular attention.
The prize, established in 1985 and originally intended to be awarded periodically, is now awarded annually for contributions to the advancement of applied mathematics on the national or international level.
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.