Hubert Chan, T-H.; Hu, Shuguang; Jiang, Shaofeng H.-C. A PTAS for the Steiner forest problem in doubling metrics. (English) Zbl 1398.68677 SIAM J. Comput. 47, No. 4, 1705-1734 (2018). MSC: 68W25 68R10 68W20 PDF BibTeX XML Cite \textit{T-H. Hubert Chan} et al., SIAM J. Comput. 47, No. 4, 1705--1734 (2018; Zbl 1398.68677) Full Text: DOI arXiv OpenURL
Feldmann, Andreas Emil; Fung, Wai Shing; Könemann, Jochen; Post, Ian A \((1+\varepsilon)\)-embedding of low highway dimension graphs into bounded treewidth graphs. (English) Zbl 1398.68672 SIAM J. Comput. 47, No. 4, 1667-1704 (2018). MSC: 68W25 68Q25 90B06 90C35 PDF BibTeX XML Cite \textit{A. E. Feldmann} et al., SIAM J. Comput. 47, No. 4, 1667--1704 (2018; Zbl 1398.68672) Full Text: DOI OpenURL
Mukhopadhyay, Sagnik; Radhakrishnan, Jaikumar; Sanyal, Swagato Separation between deterministic and randomized query complexity. (English) Zbl 1396.68045 SIAM J. Comput. 47, No. 4, 1644-1666 (2018). MSC: 68Q05 68Q10 68Q25 PDF BibTeX XML Cite \textit{S. Mukhopadhyay} et al., SIAM J. Comput. 47, No. 4, 1644--1666 (2018; Zbl 1396.68045) Full Text: DOI OpenURL
Chekuri, Chandra; Sidiropoulos, Anastasios Approximation algorithms for Euler genus and related problems. (English) Zbl 1398.68663 SIAM J. Comput. 47, No. 4, 1610-1643 (2018). MSC: 68W25 05C10 05C85 68R10 68W40 PDF BibTeX XML Cite \textit{C. Chekuri} and \textit{A. Sidiropoulos}, SIAM J. Comput. 47, No. 4, 1610--1643 (2018; Zbl 1398.68663) Full Text: DOI arXiv OpenURL
Kaplan, Haim; Mulzer, Wolfgang; Roditty, Liam; Seiferth, Paul Spanners for directed transmission graphs. (English) Zbl 1398.68401 SIAM J. Comput. 47, No. 4, 1585-1609 (2018). MSC: 68R10 05C20 05C85 68P05 68Q25 68W40 PDF BibTeX XML Cite \textit{H. Kaplan} et al., SIAM J. Comput. 47, No. 4, 1585--1609 (2018; Zbl 1398.68401) Full Text: DOI arXiv OpenURL
Gandikota, Venkata; Ghazi, Badih; Grigorescu, Elena NP-hardness of Reed-Solomon decoding, and the Prouhet-Tarry-Escott problem. (English) Zbl 1444.94131 SIAM J. Comput. 47, No. 4, 1547-1584 (2018). MSC: 94B35 94B05 PDF BibTeX XML Cite \textit{V. Gandikota} et al., SIAM J. Comput. 47, No. 4, 1547--1584 (2018; Zbl 1444.94131) Full Text: DOI arXiv OpenURL
Hubert Chan, T-H.; Chen, Fei; Wu, Xiaowei; Zhao, Zhichao Ranking on arbitrary graphs: rematch via continuous linear programming. (English) Zbl 1398.68400 SIAM J. Comput. 47, No. 4, 1529-1546 (2018). MSC: 68R10 05C70 68W20 90C35 PDF BibTeX XML Cite \textit{T-H. Hubert Chan} et al., SIAM J. Comput. 47, No. 4, 1529--1546 (2018; Zbl 1398.68400) Full Text: DOI OpenURL
Chakrabarty, Deeparnab; Ene, Alina; Krishnaswamy, Ravishankar; Panigrahi, Debmalya Online buy-at-bulk network design. (English) Zbl 1396.68135 SIAM J. Comput. 47, No. 4, 1505-1528 (2018). MSC: 68W27 68R10 68W25 90B10 90C27 PDF BibTeX XML Cite \textit{D. Chakrabarty} et al., SIAM J. Comput. 47, No. 4, 1505--1528 (2018; Zbl 1396.68135) Full Text: DOI arXiv OpenURL
Kawarabayashi, Ken-ichi; Kobayashi, Yusuke All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs. (English) Zbl 1392.05050 SIAM J. Comput. 47, No. 4, 1483-1504 (2018). MSC: 05C21 05C10 05C85 68W25 90C27 PDF BibTeX XML Cite \textit{K.-i. Kawarabayashi} and \textit{Y. Kobayashi}, SIAM J. Comput. 47, No. 4, 1483--1504 (2018; Zbl 1392.05050) Full Text: DOI OpenURL
Buchbinder, Niv; Naor, Joseph; Schwartz, Roy Simplex partitioning via exponential clocks and the multiway-cut problem. (English) Zbl 1397.68220 SIAM J. Comput. 47, No. 4, 1463-1482 (2018). MSC: 68W25 05C70 05C85 68U05 68W20 PDF BibTeX XML Cite \textit{N. Buchbinder} et al., SIAM J. Comput. 47, No. 4, 1463--1482 (2018; Zbl 1397.68220) Full Text: DOI OpenURL
Li, Fu; Tzameret, Iddo; Wang, Zhengyu Characterizing propositional proofs as noncommutative formulas. (English) Zbl 1426.03037 SIAM J. Comput. 47, No. 4, 1424-1462 (2018). Reviewer: Saeed Salehi (Tabriz) MSC: 03F20 03B05 03D15 68Q15 68Q17 PDF BibTeX XML Cite \textit{F. Li} et al., SIAM J. Comput. 47, No. 4, 1424--1462 (2018; Zbl 1426.03037) Full Text: DOI arXiv OpenURL
Canonne, Clément L.; Gouleakis, Themis; Rubinfeld, Ronitt Sampling correctors. (English) Zbl 1397.68216 SIAM J. Comput. 47, No. 4, 1373-1423 (2018). MSC: 68W20 PDF BibTeX XML Cite \textit{C. L. Canonne} et al., SIAM J. Comput. 47, No. 4, 1373--1423 (2018; Zbl 1397.68216) Full Text: DOI OpenURL
Allender, Eric; Grochow, Joshua A.; van Melkebeek, Dieter; Moore, Cristopher; Morgan, Andrew Minimum circuit size, graph isomorphism, and related problems. (English) Zbl 1397.68082 SIAM J. Comput. 47, No. 4, 1339-1372 (2018). MSC: 68Q15 05C60 68Q17 68Q30 PDF BibTeX XML Cite \textit{E. Allender} et al., SIAM J. Comput. 47, No. 4, 1339--1372 (2018; Zbl 1397.68082) Full Text: DOI arXiv OpenURL
Feldman, Vitaly; Perkins, Will; Vempala, Santosh On the complexity of random satisfiability problems with planted solutions. (English) Zbl 1396.68057 SIAM J. Comput. 47, No. 4, 1294-1338 (2018). MSC: 68Q25 05C65 05C70 05C80 68Q17 68Q87 PDF BibTeX XML Cite \textit{V. Feldman} et al., SIAM J. Comput. 47, No. 4, 1294--1338 (2018; Zbl 1396.68057) Full Text: DOI OpenURL
Bateni, Mohammad Hossein; Hajiaghayi, Mohammad Taghi; Liaghat, Vahid Improved approximation algorithms for (budgeted) node-weighted Steiner problems. (English) Zbl 1396.68134 SIAM J. Comput. 47, No. 4, 1275-1293 (2018). MSC: 68W25 05C85 68R10 PDF BibTeX XML Cite \textit{M. H. Bateni} et al., SIAM J. Comput. 47, No. 4, 1275--1293 (2018; Zbl 1396.68134) Full Text: DOI OpenURL