Subjects -> MATHEMATICS (Total: 1013 journals)
    - APPLIED MATHEMATICS (92 journals)
    - GEOMETRY AND TOPOLOGY (23 journals)
    - MATHEMATICS (714 journals)
    - MATHEMATICS (GENERAL) (45 journals)
    - NUMERICAL ANALYSIS (26 journals)
    - PROBABILITIES AND MATH STATISTICS (113 journals)

APPLIED MATHEMATICS (92 journals)

Showing 1 - 82 of 82 Journals sorted alphabetically
Advances in Applied Mathematics     Full-text available via subscription   (Followers: 15)
Advances in Applied Mathematics and Mechanics     Full-text available via subscription   (Followers: 6)
Advances in Applied Mechanics     Full-text available via subscription   (Followers: 15)
AKCE International Journal of Graphs and Combinatorics     Open Access  
American Journal of Applied Mathematics and Statistics     Open Access   (Followers: 11)
American Journal of Applied Sciences     Open Access   (Followers: 22)
American Journal of Modeling and Optimization     Open Access   (Followers: 3)
Annals of Actuarial Science     Full-text available via subscription   (Followers: 2)
Applied Mathematical Modelling     Full-text available via subscription   (Followers: 22)
Applied Mathematics and Computation     Hybrid Journal   (Followers: 31)
Applied Mathematics and Mechanics     Hybrid Journal   (Followers: 4)
Applied Mathematics and Nonlinear Sciences     Open Access  
Applied Mathematics and Physics     Open Access   (Followers: 2)
Biometrical Letters     Open Access  
British Actuarial Journal     Full-text available via subscription   (Followers: 2)
Bulletin of Mathematical Sciences and Applications     Open Access  
Communication in Biomathematical Sciences     Open Access   (Followers: 2)
Communications in Applied and Industrial Mathematics     Open Access   (Followers: 1)
Communications on Applied Mathematics and Computation     Hybrid Journal   (Followers: 1)
Differential Geometry and its Applications     Full-text available via subscription   (Followers: 4)
Discrete and Continuous Models and Applied Computational Science     Open Access  
Discrete Applied Mathematics     Hybrid Journal   (Followers: 10)
Doğuş Üniversitesi Dergisi     Open Access  
e-Journal of Analysis and Applied Mathematics     Open Access  
Engineering Mathematics Letters     Open Access   (Followers: 1)
European Actuarial Journal     Hybrid Journal  
Foundations and Trends® in Optimization     Full-text available via subscription   (Followers: 3)
Frontiers in Applied Mathematics and Statistics     Open Access   (Followers: 1)
Fundamental Journal of Mathematics and Applications     Open Access  
International Journal of Advances in Applied Mathematics and Modeling     Open Access   (Followers: 1)
International Journal of Applied Mathematics and Statistics     Full-text available via subscription   (Followers: 3)
International Journal of Computer Mathematics : Computer Systems Theory     Hybrid Journal  
International Journal of Data Mining, Modelling and Management     Hybrid Journal   (Followers: 10)
International Journal of Engineering Mathematics     Open Access   (Followers: 7)
International Journal of Fuzzy Systems     Hybrid Journal  
International Journal of Swarm Intelligence     Hybrid Journal   (Followers: 2)
International Journal of Theoretical and Mathematical Physics     Open Access   (Followers: 13)
International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems     Hybrid Journal   (Followers: 3)
Journal of Advanced Mathematics and Applications     Full-text available via subscription   (Followers: 1)
Journal of Advances in Mathematics and Computer Science     Open Access  
Journal of Applied & Computational Mathematics     Open Access  
Journal of Applied Intelligent System     Open Access  
Journal of Applied Mathematics & Bioinformatics     Open Access   (Followers: 6)
Journal of Applied Mathematics and Physics     Open Access   (Followers: 9)
Journal of Computational Geometry     Open Access   (Followers: 3)
Journal of Innovative Applied Mathematics and Computational Sciences     Open Access   (Followers: 6)
Journal of Mathematical Sciences and Applications     Open Access   (Followers: 2)
Journal of Mathematics and Music: Mathematical and Computational Approaches to Music Theory, Analysis, Composition and Performance     Hybrid Journal   (Followers: 12)
Journal of Mathematics and Statistics Studies     Open Access  
Journal of Physical Mathematics     Open Access   (Followers: 2)
Journal of Symbolic Logic     Hybrid Journal   (Followers: 2)
Letters in Biomathematics     Open Access   (Followers: 1)
Mathematical and Computational Applications     Open Access   (Followers: 3)
Mathematical Models and Computer Simulations     Hybrid Journal   (Followers: 3)
Mathematics and Computers in Simulation     Hybrid Journal   (Followers: 3)
Modeling Earth Systems and Environment     Hybrid Journal   (Followers: 1)
Moscow University Computational Mathematics and Cybernetics     Hybrid Journal  
Multiscale Modeling and Simulation     Hybrid Journal   (Followers: 2)
Pacific Journal of Mathematics for Industry     Open Access  
Partial Differential Equations in Applied Mathematics     Open Access   (Followers: 1)
Ratio Mathematica     Open Access  
Results in Applied Mathematics     Open Access   (Followers: 1)
Scandinavian Actuarial Journal     Hybrid Journal   (Followers: 2)
SIAM Journal on Applied Dynamical Systems     Hybrid Journal   (Followers: 3)
SIAM Journal on Applied Mathematics     Hybrid Journal   (Followers: 11)
SIAM Journal on Computing     Hybrid Journal   (Followers: 11)
SIAM Journal on Control and Optimization     Hybrid Journal   (Followers: 18)
SIAM Journal on Discrete Mathematics     Hybrid Journal   (Followers: 8)
SIAM Journal on Financial Mathematics     Hybrid Journal   (Followers: 3)
SIAM Journal on Imaging Sciences     Hybrid Journal   (Followers: 7)
SIAM Journal on Mathematical Analysis     Hybrid Journal   (Followers: 4)
SIAM Journal on Matrix Analysis and Applications     Hybrid Journal   (Followers: 3)
SIAM Journal on Numerical Analysis     Hybrid Journal   (Followers: 7)
SIAM Journal on Optimization     Hybrid Journal   (Followers: 12)
SIAM Journal on Scientific Computing     Hybrid Journal   (Followers: 16)
SIAM Review     Hybrid Journal   (Followers: 9)
SIAM/ASA Journal on Uncertainty Quantification     Hybrid Journal   (Followers: 2)
Swarm Intelligence     Hybrid Journal   (Followers: 3)
Theory of Probability and its Applications     Hybrid Journal   (Followers: 2)
Uniform Distribution Theory     Open Access  
Universal Journal of Applied Mathematics     Open Access   (Followers: 2)
Universal Journal of Computational Mathematics     Open Access   (Followers: 3)
Similar Journals
Journal Cover
SIAM Journal on Computing
Journal Prestige (SJR): 0.874
Citation Impact (citeScore): 2
Number of Followers: 11  
 
  Hybrid Journal Hybrid journal (It can contain Open Access articles)
ISSN (Print) 0097-5397 - ISSN (Online) 1095-7111
Published by Society for Industrial and Applied Mathematics Homepage  [17 journals]
  • Special Section on the Fifty-Second Annual ACM Symposium on the Theory of
           Computing (STOC 2020)

    • Free pre-print version: Loading...

      Authors: Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page STOC20-i-STOC20-i, June 2022.
      This issue of SICOMP contains six specially selected papers from STOC 2020, the Fifty-second Annual ACM Symposium on the Theory of Computing, which was held June 22--26, 2020, initially planned at Chicago, Illinois, but due to COVID-19 was an online conference in the end. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough reviewing process of SICOMP. The program committee for STOC 2020 consisted of an executive committee made up of Nima Anari, Boaz Barak, Sébastien Bubeck, Mark Bun, Arkadev Chattopadhyay, Chandra Chekuri, Julia Chuzhoy, Marek Cygan, Ilias Diakonikolas, Yevgeniy Dodis, Sebastian Forster, Ankit Garg, Nika Haghtalab, Prahladh Harsha, Justin Holmgren, Piotr Indyk, Rahul Jain, Sanjeev Khanna, Dakshita Khurana, Pravesh Kothari, Robert Krauthgamer, Marvin Künnemann, Tengyu Ma, Rafael Oliveira, Merav Parter, Sofya Raskhodnikova, Robert Robere, Dana Ron, Noga Ron-Zewi, Thatchaphol Saranurak, Balasubramanian Sivan, Christian Sohler, Madhur Tulsiani, Omri Weinstein, Christian Wulff-Nilsen, and Henry Yuen. The program chair was Julia Chuzhoy. Included in this issue are the following papers: ``Explicit Near-Ramanujan Graphs of Every Degree" by Sidhanth Mohanty, Ryan O'Donnell, and Pedro Paredes shows a deterministic poly$(n)$-time algorithm that outputs a $d$-regular graph on $\Theta(n)$ vertices that is $\epsilon$-near-Ramanujan. ``Reducing Path TSP to TSP" by Vera Traub, Jens Vygen, and Rico Zenklusen presents a black-box reduction from the path version of the traveling salesman problem (Path TSP) to the classical tour version (TSP). ``Nearly Optimal Static Las Vegas Succinct Dictionary" by Huacheng Yu obtains a randomized dictionary data structure using ${OPT}+{poly}\lg n+O(\lg^{(\ell)} U)$ bits of space with expected constant query time for the static dictionary problem. ``Separating the Communication Complexity of Truthful and Nontruthful Algorithms for Combinatorial Auctions" by Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh Raj Saxena, and S. Matthew Weinberg provides the first separation in the approximation guarantee achievable by truthful and nontruthful combinatorial auctions with polynomial communication. ``Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization" by Lijie Chen and Hanlin Ren establish a connection between nondeterministic algorithms estimating the acceptance probability of a given circuit and average-case lower bounds for nondeterministic time classes. ``Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs" by Siddharth Bhandari and Sayantan Chakraborty presents a randomized algorithm that takes as input an undirected $n$-vertex graph $G$ with maximum degree $\Delta$ and an integer $k>3\Delta$ and returns a random proper $k$-coloring of $G$. We thank the authors, the STOC 2020 program committee, the STOC 2020 external reviewers, and the SICOMP referees for all of their hard work. Arkadev Chattopadhyay, Marek Cygan, Noga Ron-Zewi, Christian Wulff-Nilsen - Guest editors
      Citation: SIAM Journal on Computing
      PubDate: 2022-06-24T07:00:00Z
      DOI: 10.1137/22N975494
      Issue No: Vol. 51, No. 3 (2022)
       
  • Satisfiability in MultiValued Circuits

    • Free pre-print version: Loading...

      Authors: Paweł M. Idziak, Jacek Krzaczkowski
      Pages: 337 - 378
      Abstract: SIAM 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 monotone gates or linear gates. We go outside the Boolean realm and consider circuits built of any fixed set of gates on an arbitrarily large finite domain. From the complexity point of view this is connected with solving equations over finite algebras. We want to characterize finite algebras A with a polynomial time algorithm deciding if an equation over A has a solution. We are also looking for a polynomial time algorithm deciding if two circuits over a finite algebra compute the same function. Although we have not managed to solve these problems in the most general setting we have obtained such a characterization (in terms of nice structural algebraic properties) for a very broad class of algebras from congruence modular varieties, including groups, rings, and lattices and their extensions.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-05T07:00:00Z
      DOI: 10.1137/18M1220194
      Issue No: Vol. 51, No. 3 (2022)
       
  • On a Combinatorial Generation Problem of Knuth

    • Free pre-print version: Loading...

      Authors: Arturo Merino, Ondřej Mička, Torsten Mütze
      Pages: 379 - 423
      Abstract: SIAM 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 2(n+1) with exactly n+1 many 0s and 1s can be ordered cyclically so that any two consecutive strings differ in swapping the first bit with a complementary bit at some later position. In his book The Art of Computer Programming, Knuth raised a stronger form of this conjecture (Problem 56 in section 7.2.1.3), which requires that the sequence of positions with which the first bit is swapped in each step of such an ordering has 2n+1 blocks of the same length, and each block is obtained by adding s=1 (modulo 2n+1) to the previous block. In this work, we prove Knuth's conjecture in a more general form, allowing for arbitrary shifts $s\geq 1$ that are coprime to 2n+1. We also present an algorithm to compute this ordering, generating each new bitstring in $\mathcal{O}(n)$ time, using $\mathcal{O}(n)$ memory in total.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-05T07:00:00Z
      DOI: 10.1137/20M1377394
      Issue No: Vol. 51, No. 3 (2022)
       
  • Sorting Short Keys in Circuits of Size ${o(n \log n)}$

    • Free pre-print version: Loading...

      Authors: Gilad Asharov, Wei-Kai Lin, Elaine Shi
      Pages: 424 - 466
      Abstract: SIAM 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 described with a $k$-bit comparison key and a $w$-bit payload. A long-standing open problem is whether there exist $(k + w) \cdot o(n \log n)$-sized Boolean circuits for sorting. A landmark result in this area is the work by Ajtai, Komlós, and Szemerédi (An $O(n \log n)$ sorting network, STOC'83), where they showed how to achieve sorting circuits with $(k + w) \cdot O(n \log n)$ Boolean gates. The recent work of Farhadi et al. (Lower bounds for external memory integer sorting via network coding, STOC'19) showed that if the famous Li-Li network coding conjecture is true, then sorting circuits of size $w \cdot o(n \log n)$ do not exist for general $k$; however, no unconditional lower bound is known (in fact proving superlinear circuit lower bounds in general is out of the reach of existing techniques). In this paper, we show that one can overcome the $n\log n$ barrier when the keys to be sorted are short. Specifically, we prove that there is a circuit with $(k + w) \cdot O(n k) \cdot (\log^*n - \log^* (w + k))^{2+\epsilon}$ Boolean gates capable of sorting any input array containing $n$ elements, each described with a $k$-bit key and a $w$-bit payload. Therefore, if the keys to be sorted are short, say, $k < o(\log n)$, our result is asymptotically better than the classical Ajtai, Komlós, and Szemerédi sorting network (ignoring ${\sf poly}\log^*$ terms); and we also overcome the $n \log n$ barrier in such cases. Such a result might be surprising initially because it is long known that comparator-based techniques must incur $\Omega(n \log n)$ comparator gates even when the keys to be sorted are only 1-bit long (e.g., see Knuth's “Art of Programming” textbook). To the best of our knowledge, we are the first to achieve nontrivial results for sorting circuits using non-comparison-based techniques. We also show that if the Li-Li network coding conjecture is true, our upper bound is optimal, barring ${\sf poly}\log^*$ terms, for every $k$ as long as $k = O(\log n)$.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-05T07:00:00Z
      DOI: 10.1137/20M1380983
      Issue No: Vol. 51, No. 3 (2022)
       
  • Optimal (Euclidean) Metric Compression

    • Free pre-print version: Loading...

      Authors: Piotr Indyk, Tal Wagner
      Pages: 467 - 491
      Abstract: SIAM 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 distortion, using as few bits as possible. We give asymptotically tight bounds for this problem, for Euclidean metrics, for $\ell_1$ (also known as Manhattan)-metrics, and for general metrics. Our bounds for Euclidean metrics mark the first improvement over compression schemes based on discretizing the classical dimensionality reduction theorem of Johnson and Lindenstrauss [Contemp. Math. 26 (1984), pp. 189--206]. Since it is known that no better dimension reduction is possible, our results establish that Euclidean metric compression is possible beyond dimension reduction.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-10T07:00:00Z
      DOI: 10.1137/20M1371324
      Issue No: Vol. 51, No. 3 (2022)
       
  • On the Complexity of Optimal Lottery Pricing and Randomized Mechanisms for
           a Unit-Demand Buyer

    • Free pre-print version: Loading...

      Authors: Xi Chen, Ilias Diakonikolas, Anthi Orfanou, Dimitris Paparas, Xiaorui Sun, Mihalis Yannakakis
      Pages: 492 - 548
      Abstract: SIAM 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 single unit-demand buyer with item values drawn from independent distributions. Optimal solutions to both problems are characterized by a linear program with exponentially many variables. For the menu size complexity of the optimal lottery problem, we present an explicit, simple instance with distributions of support size 2, and show that exponentially many lotteries are required to achieve the optimal revenue. We also show that, when distributions have support size 2 and share the same high value, the simpler scheme of item pricing can achieve the same revenue as the optimal menu of lotteries. The same holds for the case of two items with support size 2 (but not necessarily the same high value). For the computational complexity of the optimal mechanism design problem, we show that unless the polynomial-time hierarchy collapses (more exactly, ${P}^{{NP}}={P}^{{\#P}}$), there is no efficient randomized algorithm to implement an optimal mechanism even when distributions have support size 3.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-12T07:00:00Z
      DOI: 10.1137/17M1136481
      Issue No: Vol. 51, No. 3 (2022)
       
  • Elastic-Degenerate String Matching via Fast Matrix Multiplication

    • Free pre-print version: Loading...

      Authors: Giulia Bernardini, Paweł Gawrychowski, Nadia Pisanti, Solon P. Pissis, Giovanna Rosone
      Pages: 549 - 576
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 549-576, June 2022.
      An elastic-degenerate (ED) string is a sequence of $n$ sets of strings of total length $N$ which was recently proposed to model a set of similar sequences. The ED string matching (EDSM) problem is to find all occurrences of a pattern of length $m$ in an ED text. The EDSM problem has recently received some attention in the combinatorial pattern matching community, and an $\mathcal{O}(nm^{1.5}\sqrt{\log m} + N)$-time algorithm is known [Aoyama et al., CPM 2018]. The standard assumption in the prior work on this question is that $N$ is substantially larger than both $n$ and $m$, and thus we would like to have a linear dependency on the former. Under this assumption, the natural open problem is whether we can decrease the 1.5 exponent in the time complexity, similarly as in the related (but, to the best of our knowledge, not equivalent) word break problem [Backurs and Indyk, FOCS 2016]. Our starting point is a conditional lower bound for the EDSM problem. We use the popular combinatorial Boolean matrix multiplication (BMM) conjecture stating that there is no truly subcubic combinatorial algorithm for BMM [Abboud and Williams, FOCS 2014]. By designing an appropriate reduction, we show that a combinatorial algorithm solving the EDSM problem in $\mathcal{O}(nm^{1.5-\epsilon} + N)$ time, for any $\epsilon>0$, refutes this conjecture. Our reduction should be understood as an indication that decreasing the exponent requires fast matrix multiplication. String periodicity and fast Fourier transform are two standard tools in string algorithms. Our main technical contribution is that we successfully combine these tools with fast matrix multiplication to design a noncombinatorial $\tilde{\mathcal{O}}(nm^{\omega-1}+N)$-time algorithm for EDSM, where $\omega$ denotes the matrix multiplication exponent and the $\tilde{\mathcal{O}}(\cdot)$ notation suppresses polylog factors. To the best of our knowledge, we are the first to combine these tools. In particular, using the fact that $\omega
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-19T07:00:00Z
      DOI: 10.1137/20M1368033
      Issue No: Vol. 51, No. 3 (2022)
       
  • Constraint Satisfaction Problems with Global Modular Constraints:
           Algorithms and Hardness via Polynomial Representations

    • Free pre-print version: Loading...

      Authors: Joshua Brakensiek, Sivakanth Gopi, Venkatesan Guruswami
      Pages: 577 - 626
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 577-626, June 2022.
      We study the complexity of Boolean constraint satisfaction problems (CSPs) when the assignment must have Hamming weight in some congruence class modulo $M$, for various choices of the modulus $M$. Due to the known classification of tractable Boolean CSPs, this mainly reduces to the study of three cases: 2-SAT, HORN-SAT, and LIN-2 (linear equations mod 2). We classify the moduli $M$ for which these respective problems are polynomial time solvable, and when they are not (assuming the exponential time hypothesis). Our study reveals that this modular constraint lends a surprising richness to these classic, well-studied problems, with interesting broader connections to complexity theory and coding theory. The HORN-SAT case is connected to the covering complexity of polynomials representing the NAND function mod $M$. The LIN-2 case is tied to the sparsity of polynomials representing the OR function mod $M$, which in turn has connections to modular weight distribution properties of linear codes and locally decodable codes. In both cases, the analysis of our algorithm as well as the hardness reduction rely on these polynomial representations, highlighting an interesting algebraic common ground between hard cases for our algorithms and the gadgets which show hardness. These new complexity measures of polynomial representations merit further study. The inspiration for our study comes from a recent work by Nägele, Sudakov, and Zenklusen on submodular minimization with a global congruence constraint. Our algorithm for HORN-SAT has strong similarities to their algorithm, and in particular identical kinds of set systems arise in both cases. Our connection to polynomial representations leads to a simpler analysis of such set systems and also sheds light on (but does not resolve) the complexity of submodular minimization with a congruency requirement modulo a composite $M$.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-19T07:00:00Z
      DOI: 10.1137/19M1291054
      Issue No: Vol. 51, No. 3 (2022)
       
  • Optimal Algorithms for Geometric Centers and Depth

    • Free pre-print version: Loading...

      Authors: Timothy M. Chan, Sariel Har-Peled, Mitchell Jones
      Pages: 627 - 663
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 627-663, June 2022.
      We develop a general randomized technique for solving implicit linear programming problems, where the collection of constraints are defined implicitly by an underlying ground set of elements. In many cases, the structure of the implicitly defined constraints can be used to obtain faster linear program solvers. We apply this technique to obtain near-optimal algorithms for a variety of fundamental problems in geometry. For a given point set $P$ of size $n$ in $\mathbb{R}^d$, we develop algorithms for computing geometric centers of a point set, including the centerpoint and the Tukey median, and several other more involved measures of centrality. For $d=2$, the new algorithms run in $O(n\log n)$ expected time, which is optimal, and for higher constant $d>2$, the expected time bound is within one logarithmic factor of $O(n^{d-1})$, which is also likely near optimal for some of the problems.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-19T07:00:00Z
      DOI: 10.1137/21M1423324
      Issue No: Vol. 51, No. 3 (2022)
       
  • Matrices of Optimal Tree-Depth and a Row-Invariant Parameterized Algorithm
           for Integer Programming

    • Free pre-print version: Loading...

      Authors: Timothy F. Chan, Jacob W. Cooper, Martin Koutecký, Daniel Král, Kristýna Pekárková
      Pages: 664 - 700
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 664-700, June 2022.
      A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with $n$ variables and a constraint matrix with dual tree-depth $d$ and largest entry $\Delta$ are solvable in time $g(d,\Delta){poly}(n)$ for some function $g$. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time $g(d^*,\Delta){poly}(n)$ where $d^*$ is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-24T07:00:00Z
      DOI: 10.1137/20M1353502
      Issue No: Vol. 51, No. 3 (2022)
       
  • Almost Tight Bounds for Reordering Buffer Management

    • Free pre-print version: Loading...

      Authors: Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke
      Pages: 701 - 722
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 701-722, June 2022.
      We give almost tight bounds for the online reordering buffer management problem on the uniform metric. Specifically, we present the first nontrivial lower bounds for this problem by showing that deterministic online algorithms have a competitive ratio of at least $\Omega(\sqrt{\log k/\log\log k})$ and randomized online algorithms have a competitive ratio of at least $\Omega(\log\log k)$, where $k$ denotes the size of the buffer. We complement this by presenting a deterministic online algorithm for the reordering buffer management problem that obtains a competitive ratio of $O(\sqrt{\log k})$, almost matching the lower bound. This improves upon an algorithm by Avigdor-Elgrabli and Rabani that achieves a competitive ratio of $O(\log k/\log\log k)$.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-24T07:00:00Z
      DOI: 10.1137/20M1326167
      Issue No: Vol. 51, No. 3 (2022)
       
  • Nearly Optimal Planar $k$ Nearest Neighbors Queries under General Distance
           Functions

    • Free pre-print version: Loading...

      Authors: Chih-Hung Liu
      Pages: 723 - 765
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 723-765, June 2022.
      We study the $k$ nearest neighbors problem in the plane for general, convex, pairwise disjoint sites of constant description complexity such as line segments, disks, and quadrilaterals under a general family of distance functions including the $L_p$ norms and additively weighted Euclidean distances. We compose a static data structure for this general setting with nearly optimal $O(n\log\log n)$ space, optimal $O(\log n+k)$ query time, and optimal expected $O(n\log n)$ preprocessing time. We also devise a dynamic data structure (that allows insertions and deletions of sites) with $O(n\log n)$ space, $O(\log^2n+k\log n)$ query time, and expected amortized $O(\log^2 n)$ insertion time and $O(\log^4n)$ deletion time, matching the best known time complexities for point sites in the Euclidean metric and improving many applications such as dynamic minimum spanning trees in a general planar metric and dynamic connectivity in disk intersection graphs. Our results, to some extent, indicate that for the $k$ nearest neighbors problem, general distance functions may share the same time complexities with point sites in the Euclidean metric. To achieve this progress, we design vertical shallow cuttings of linear size for general distance functions. Vertical shallow cuttings are a key technique to tackle the $k$ nearest neighbors problem for point sites in the Euclidean metric, while existing generalizations to general distance functions are either not vertical or not of linear size. Our innovation is a new random sampling technique for the analysis of geometric structures, and since this technique provides a new way to develop geometric algorithms, we believe it is of independent interest.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-26T07:00:00Z
      DOI: 10.1137/20M1388371
      Issue No: Vol. 51, No. 3 (2022)
       
  • A Framework for the Secretary Problem on the Intersection of Matroids

    • Free pre-print version: Loading...

      Authors: Moran Feldman, Ola Svensson, Rico Zenklusen
      Pages: 766 - 819
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 766-819, June 2022.
      The secretary problem became one of the most prominent online selection problems due to its numerous applications in online mechanism design. The task is to select a maximum weight subset of elements subject to given constraints, where elements arrive one-by-one in random order, revealing a weight upon arrival. The decision whether to select an element has to be taken immediately after its arrival. The different applications that map to the secretary problem ask for different constraint families to be handled. The most prominent ones are matroid constraints, which both capture many relevant settings and admit strongly competitive secretary algorithms. However, dealing with more involved constraints proved to be much more difficult, and strong algorithms are known only for a few specific settings. In this paper, we present a general framework for dealing with the secretary problem over the intersection of several matroids. This framework allows us to combine and exploit the large set of matroid secretary algorithms known in the literature. As one consequence, we get constant-competitive secretary algorithms over the intersection of any constant number of matroids whose corresponding (single-)matroid secretary problems are currently known to have a constant-competitive algorithm. Moreover, we show that our results extend to submodular objectives.
      Citation: SIAM Journal on Computing
      PubDate: 2022-06-14T07:00:00Z
      DOI: 10.1137/21M1411822
      Issue No: Vol. 51, No. 3 (2022)
       
  • A Short List of Equalities Induces Large Sign-Rank

    • Free pre-print version: Loading...

      Authors: Arkadev Chattopadhyay, Nikhil S. Mande
      Pages: 820 - 848
      Abstract: SIAM Journal on Computing, Volume 51, Issue 3, Page 820-848, June 2022.
      We exhibit a natural function $F_n$ on $n$ variables that can be computed by just a linear-size decision list of “Equalities,” but whose sign-rank is $2^{\Omega(n^{1/4})}$. This yields the following two new unconditional complexity class separations. 1. Boolean circuit complexity. The function $F_n$ can be computed by linear-size depth-two threshold formulas when the weights of the threshold gates are unrestricted (${THR} \circ {THR}$), but any ${THR} \circ {MAJ}$ circuit (the weights of the bottom threshold gates are polynomially bounded in $n$) computing $F_n$ requires size $2^{\Omega(n^{1/4})}$. This provides the first separation between the Boolean circuit complexity classes ${THR} \circ {MAJ}$ and ${THR} \circ {THR}$. While Amano and Maruoka [Proceedings of the 30th International Symposium on Mathematical Foundations of Computer Science, 2005, pp. 107--118] and Hansen and Podolskii [Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010, pp. 270--279] emphasized that superpolynomial separations between the two classes remained a basic open problem, our separation is in fact exponential. In contrast, Goldmann, H\aastad, and Razborov [Comput. Complexity, 2 (1992), pp. 277--300] showed more than twenty-five years ago that functions efficiently computable by ${MAJ} \circ {THR}$ circuits can also be efficiently computed by ${MAJ} \circ {MAJ}$ circuits. In view of this, it was not even clear if ${THR} \circ {THR}$ was significantly more powerful than ${THR} \circ {MAJ}$ until our work, and there was no candidate function identified for the potential separation. 2. Communication complexity. The function $F_n$ (under the natural partition of the inputs) lies in the communication complexity class ${P}^{{MA}}$. Since $F_n$ has large sign-rank, this implies ${P}^{{MA}} \nsubseteq {UPP}$, strongly resolving a recent open problem posed by Göös, Pitassi, and Watson [Comput. Complexity, 27 (2018), pp. 245--304]. In order to prove our main result, we view $F_n$ as an ${XOR}$ function and develop a technique to lower bound the sign-rank of such functions. This requires novel approximation-theoretic arguments against polynomials of unrestricted degree. Further, our work highlights for the first time the class “decision lists of exact thresholds” as a common frontier for making progress on longstanding open problems in threshold circuits and communication complexity.
      Citation: SIAM Journal on Computing
      PubDate: 2022-06-14T07:00:00Z
      DOI: 10.1137/19M1271348
      Issue No: Vol. 51, No. 3 (2022)
       
  • Special Section on the Forty-Ninth Annual ACM Symposium on the Theory of
           Computing (STOC 2017)

    • Free pre-print version: Loading...

      Authors: Andy Drucker, Ravi Kumar, Amit Sahai, Mohit Singh
      Abstract: SIAM Journal on Computing, Volume 51, Issue 2, Page Si-Sii, April 2022.
      This issue of SICOMP contains ten specially selected papers from STOC 2017, the Forty-ninth Annual ACM Symposium on the Theory of Computing, which was held June 19--23 in Montreal, Canada. The papers here were chosen to represent the range and quality of the STOC program. These papers have been revised and extended by their authors and subjected to the standard thorough reviewing process of SICOMP. The program committee for STOC 2017 consisted of Nina Balcan, Allan Borodin, Keren Censor-Hillel, Edith Cohen, Artur Czumaj, Yevgeniy Dodis, Andrew Drucker, Nick Harvey, Monika Henzinger, Russell Impagliazzo, Ken-ichi Kawarabayashi, Ravi Kumar, James R. Lee, Katrina Ligett, Aleksander M'dry, Cristopher Moore, Jelani Nelson, Eric Price, Amit Sahai, Jared Saia, Shubhangi Saraf, Alexander Sherstov, Mohit Singh, and Gábor Tardos. The program chair was Valerie King. Included in this issue are the following papers: ``Short Presburger Arithmetic Is Hard," by Danny Nguyen and Igor Pak, proves that the satisfiability of short sentences in Presburger arithmetic with $m+2$ alternating quantifiers is $\Sigma^{{P}}_m$-complete or $\Pi^{{P}}_m$-complete when the first quantifier is $\exists$ or $\forall$, respectively. ``An Efficient Reduction from Two-Source to Nonmalleable Extractors: Achieving Near-Logarithmic Min-Entropy," by Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma, gets an explicit bipartite Ramsey graph (or a twosource extractor) for sets of size 2$k$ for $k = O(\log n \log \log n)$, using the currently best explicit nonmalleable extractors. ``Holographic Algorithm with Matchgates Is Universal for Planar \#CSP over Boolean Domain," by Jin-Yi Cai and Zhiguo Fu, classifies all counting CSPs over Boolean variables into one of three categories: polynomial-time tractable, \#P-hard for general instances but solvable in polynomial time over planar graphs, and \#P-hard over planar graphs. ``Deciding Parity Games in Quasipolynomial Time," by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan, shows the parameterized parity game, with $n$ nodes and $m$ priorities, is in the class of fixed parameter tractable problems when parameterized over $m$. ``New Hardness Results for Routing on Disjoint Paths," by Julia Chuzhoy, David H. K. Kim, and Rachit Nimavat, proves that node-disjoint paths is $2^{\Omega(\sqrt{\log n})}$-hard to approximate, unless all problems in NP have algorithms with running time $n^{O(\log n)}$. ``A Weighted Linear Matroid Parity Algorithm," by Satoru Iwata and Yusuke Kobayashi, presents a combinatorial, deterministic, strongly polynomial-time algorithm for the weighted linear matroid parity problem. ``Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace," by William M. Hoza and Chris Umans, shows that $\mathbf{BPL} \subseteq \bigcap_{\alpha> 0} {DSPACE}(\log^{1 + \alpha} n)$, assuming that for every derandomization result for log-space algorithms there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. ``Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs," by Pravesh K. Kothari, Raghu Meka, and Prasad Raghavendra, shows that for CSPs, subexponential size LP relaxations are as powerful as $n^{\Omega(1)}$-rounds of the Sherali--Adams LP hierarchy. ``Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation in the Plain Model," by Ran Canetti, Oxana Poburinnaya, and Muthuramakrishnan Venkitasubramaniam, defines a new type of encryption and shows that Yao's garbling scheme, implemented with this encryption mechanism, is secure against adaptive adversaries. ``Geodesic Walks in Polytopes," by Yin Tat Lee and Santosh Vempala, introduces the geodesic walk for sampling Riemannian manifolds and applies it to the problem of generating uniform random points from the interior of polytopes in ${\mathbb{R}}^{n}$ specified by m inequalities; the resulting sampling algorithm for polytopes mixes in $O^{*}(mn^{\frac{3}{4}})$ steps. We thank the authors, the STOC 2017 program committee, the STOC 2017 external reviewers, and the SICOMP referees for all of their hard work. Andy Drucker, Ravi Kumar, Amit Sahai, Mohit Singh, Guest editors
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-28T07:00:00Z
      DOI: 10.1137/22N975482
      Issue No: Vol. 51, No. 2 (2022)
       
  • Geodesic Walks in Polytopes

    • Free pre-print version: Loading...

      Authors: Yin Tat Lee, Santosh Vempala
      Abstract: SIAM 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 uniform random points from the interior of polytopes in $\mathbb{R}^{n}$ specified by $m$ inequalities. The walk is a discrete-time simulation of a stochastic differential equation on the Riemannian manifold equipped with the metric induced by the Hessian of a convex function; each step is the solution of an ordinary differential equation (ODE). The resulting sampling algorithm for polytopes mixes in $O^{*}(mn^{\frac{3}{4}})$ steps. This is the first walk that breaks the quadratic barrier for mixing in high dimension, improving on the previous best bound of $O^{*}(mn)$ by Kannan and Narayanan for the Dikin walk. We also show that each step of the geodesic walk (solving an ODE) can be implemented efficiently, thus improving the time complexity for sampling polytopes. Our analysis of the geodesic walk for general Hessian manifolds does not assume positive curvature and might be of independent interest.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-28T07:00:00Z
      DOI: 10.1137/17M1145999
      Issue No: Vol. 51, No. 2 (2022)
       
  • When Symmetries Are Not Enough: A Hierarchy of Hard Constraint
           Satisfaction Problems

    • Free pre-print version: Loading...

      Authors: Pierre Gillibert, Julius Jonušas, Michael Kompatscher, Antoine Mottet, Michael Pinsker
      Pages: 175 - 213
      Abstract: SIAM 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 the Hrushovski-encoding---to $\omega$-categorical structures in a possibly infinite signature. We show that the encoded structures retain desirable algebraic properties of the original structures, but that the constraint satisfaction problems (CSPs) associated with these structures can be badly behaved in terms of computational complexity. This method allows us to systematically generate $\omega$-categorical templates whose CSPs are complete for a variety of complexity classes of arbitrarily high complexity and $\omega$-categorical templates that show that membership in any given complexity class containing AC$^0$ cannot be expressed by a set of identities on the polymorphisms. It moreover enables us to prove that recent results about the relevance of topology on polymorphism clones of $\omega$-categorical structures also apply for CSP templates, i.e., structures in a finite language. Finally, we obtain a concrete algebraic criterion which could constitute a description of the delineation between tractability and NP-hardness in the dichotomy conjecture for first-order reducts of finitely bounded homogeneous structures.
      Citation: SIAM Journal on Computing
      PubDate: 2022-03-09T08:00:00Z
      DOI: 10.1137/20M1383471
      Issue No: Vol. 51, No. 2 (2022)
       
  • Anchored Parallel Repetition for Nonlocal Games

    • Free pre-print version: Loading...

      Authors: Mohammad Bavarian, Thomas Vidick, Henry Yuen
      Pages: 214 - 253
      Abstract: SIAM 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 theorem for all anchored games in the setting of quantum entangled players. This transformation is inspired in part by the Feige--Kilian transformation [SIAM J. Comput., 30 (2000), pp. 324--346], and has the property that if the quantum value of the original game $G$ is $v$, then the quantum value of the anchored game $G_{{\perp}}$ is $1 - (1 - \alpha)^2 \cdot (1 - v)$, where $\alpha$ is a parameter of the transformation. In particular the anchored game has quantum value 1 if and only if the original game $G$ has quantum value 1. This provides the first gap amplification technique for general two-player nonlocal games that achieves exponential decay of the quantum value.
      Citation: SIAM Journal on Computing
      PubDate: 2022-03-14T07:00:00Z
      DOI: 10.1137/21M1405927
      Issue No: Vol. 51, No. 2 (2022)
       
  • A Subexponential Parameterized Algorithm for Directed Subset Traveling
           Salesman Problem on Planar Graphs

    • Free pre-print version: Loading...

      Authors: Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk
      Pages: 254 - 289
      Abstract: SIAM 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 of the most fundamental graph problems, parameterized by some natural parameter $k$, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in $\mathcal{O}(\sqrt{k})$ instead of $\mathcal{O}(k)$ (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals $T$ by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number $k= T $ of terminals is regarded as the parameter. We show that Subset TSP can be solved in time $2^{\mathcal{O}(\sqrt{k}\log k)}\cdot n^{\mathcal{O}(1)}$ even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014, SIAM, Philadelphia, 2014, pp. 1812--1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-07T07:00:00Z
      DOI: 10.1137/19M1304088
      Issue No: Vol. 51, No. 2 (2022)
       
  • Metric Embedding via Shortest Path Decompositions

    • Free pre-print version: Loading...

      Authors: Ittai Abraham, Arnold Filtser, Anupam Gupta, Ofer Neiman
      Pages: 290 - 314
      Abstract: SIAM 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 a new embedding technique based on low-depth decompositions of a graph via shortest paths. The notion of shortest path decomposition (SPD) depth is inductively defined: A (weighed) path graph has SPD depth $1$. General graph has an SPD of depth $k$ if it contains a shortest path whose deletion leads to a graph, each of whose components has SPD depth at most $k-1$. In this paper we give an $O(k^{\min\{\nicefrac{1}{p},\nicefrac{1}{2}\}})$-distortion embedding for graphs of SPD depth at most $k$. This result is asymptotically tight for any fixed $p>1$, while for $p=1$ it is tight up to second order terms. As a corollary of this result, we show that graphs having pathwidth $k$ embed into $\ell_p$ with distortion $O(k^{\min\{\nicefrac{1}{p},\nicefrac{1}{2}\}})$. For $p=1$, this improves over the best previous bound of Lee and Sidiropoulos that was exponential in $k$; moreover, for other values of $p$ it gives the first embeddings whose distortion is independent of the graph size $n$. Furthermore, we use the fact that planar graphs have SPD depth $O(\log n)$ to give a new proof that any planar graph embeds into $\ell_1$ with distortion $O(\sqrt{\log n})$. Our approach also gives new results for graphs with bounded treewidth, and for graphs excluding a fixed minor.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-11T07:00:00Z
      DOI: 10.1137/19M1296021
      Issue No: Vol. 51, No. 2 (2022)
       
  • Derandomization from Algebraic Hardness

    • Free pre-print version: Loading...

      Authors: Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon
      Pages: 315 - 335
      Abstract: SIAM 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 $C$ of small enough circuit size and degree, if $C$ is nonzero, then $C\circ {{\mathsf{Gen}}}$ is nonzero. In this paper, we give a new construction of such an HSG assuming that we have an explicit polynomial of sufficient hardness. Formally, we prove the following result over any field ${\mathbb{F}}$ of characteristic zero: Let $k\in {\mathbb{N}}$ and $\delta> 0$ be arbitrary constants. Suppose ${\left\{ {P_d} \right\}}_{d\in {\mathbb{N}}}$ is an explicit family of $k$-variate polynomials such that $\deg P_d = d$ and $P_d$ requires algebraic circuits of size $d^\delta$. Then, there are explicit hitting sets of polynomial size for the class ${\mathsf{VP}}$. This is the first HSG in the algebraic setting that yields a complete derandomization of polynomial identity testing (PIT) for general circuits from a suitable algebraic hardness assumption. Unlike the prior constructions of such maps [N. Nisan and A. Wigderson, J. Comput. System Sci., 49 (1994), pp. 149--167; V. Kabanets and R. Impagliazzo, Comput. Complexity, 13 (2004), pp. 1--46; M. Agrawal, S. Ghosh, and N.Saxena, Proc. Natl. Acad. Sci. USA, 116 (2019), pp. 8107--8118; M. Kumar, R. Saptharishi, and A. Tengse, Proceedings of the \textup30th Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, pp. 639--646], our construction is purely algebraic and does not rely on the notion of combinatorial designs. As a direct consequence, we show that even saving a single point from the “trivial” explicit, exponential sized hitting sets for constant-variate polynomials of low individual degree which are computable by small circuits implies a deterministic polynomial time algorithm for PIT. More precisely, we show the following: Let $k\in {\mathbb{N}}$ and $\delta> 0$ be arbitrary constants. Suppose for every $s$ large enough, there is an explicit hitting set of size at most $((s+1)^k - 1)$ for the class of $k$-variate polynomials of individual degree $s$ that are computable by size $s^\delta$ circuits. Then there is an explicit hitting set of size ${\operatorname{poly}}(s)$ for the class of $s$-variate polynomials, of degree $s$, that are computable by size $s$ circuits. As a consequence, we give a deterministic polynomial time construction of hitting sets for algebraic circuits, if a strengthening of the $\tau$-conjecture of Shub and Smale [M. Shub and S. Smale, Duke Math. J., 81 (1995), pp. 47--54; S. Smale, Math. Intelligencer, 20 (1998), pp. 7--15] is true.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-21T07:00:00Z
      DOI: 10.1137/20M1347395
      Issue No: Vol. 51, No. 2 (2022)
       
  • Decodable Quantum LDPC Codes beyond the $\sqrt{n}$ Distance Barrier Using
           High-Dimensional Expanders

    • Free pre-print version: Loading...

      Authors: Shai Evra, Tali Kaufman, Gilles Zémor
      Abstract: SIAM Journal on Computing, Ahead of Print.
      Constructing quantum low-density parity-check (LDPC) codes with a minimum distance that grows faster than a square root of the length has been a major challenge of the field. With this challenge in mind, we investigate constructions that come from high-dimensional expanders, in particular Ramanujan complexes. These naturally give rise to very unbalanced quantum error correcting codes that have a large $X$-distance but a much smaller $Z$-distance. However, together with a classical expander LDPC code and a tensoring method that generalizes a construction of Hastings and also the Tillich--Zémor construction of quantum codes, we obtain quantum LDPC codes whose minimum distance exceeds the square root of the code length and whose dimension comes close to a square root of the code length. When the ingredient is a 2-dimensional Ramanujan complex, or the 2-skeleton of a 3-dimensional Ramanujan complex, we obtain a quantum LDPC code of minimum distance $n^{1/2}\log^{1/2}n$. We then exploit the expansion properties of the complex to devise the first polynomial-time algorithm that decodes above the square root barrier for quantum LDPC codes. Using a 3-dimensional Ramanujan complex, we also obtain an overall quantum code of minimum distance $n^{1/2}\log n$, which sets a new record for quantum LDPC codes.
      Citation: SIAM Journal on Computing
      PubDate: 2022-06-14T07:00:00Z
      DOI: 10.1137/20M1383689
       
  • An $O(\log \log m)$ Prophet Inequality for Subadditive Combinatorial
           Auctions

    • Free pre-print version: Loading...

      Authors: Paul Dütting, Thomas Kesselheim, Brendan Lucier
      Abstract: SIAM Journal on Computing, Ahead of Print.
      Prophet inequalities compare the expected performance of an online algorithm for a stochastic optimization problem to the expected optimal solution in hindsight. They are a major alternative to classic worst-case competitive analysis, of particular importance in the design and analysis of simple (posted-price) incentive compatible mechanisms with provable approximation guarantees. A central open problem in this area concerns subadditive combinatorial auctions. Here $n$ agents with subadditive valuation functions compete for the assignment of $m$ items. The goal is to find an allocation of the items that maximizes the total value of the assignment. The question is whether there exists a prophet inequality for this problem that significantly beats the best known approximation factor of $O(\log m)$. We make major progress on this question by providing an $O(\log \log m)$ prophet inequality. Our proof goes through a novel primal-dual approach. It is also constructive, resulting in an online policy that takes the form of static and anonymous item prices that can be computed in polynomial time given appropriate query access to the valuations. As an application of our approach, we construct a simple and incentive compatible mechanism based on posted prices that achieves an $O(\log \log m)$ approximation to the optimal revenue for subadditive valuations under an item-independence assumption.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-19T07:00:00Z
      DOI: 10.1137/20M1382799
       
  • Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization

    • Free pre-print version: Loading...

      Authors: Lijie Chen, Hanlin Ren
      Abstract: SIAM 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} = {NTIME}[n^{{polylog}(n)}]$ cannot be computed by polynomial-size ${ACC}^0$ circuits (constant-depth circuits consisting of ${AND}$/${OR}$/${MOD}_m$ gates for a fixed constant $m$, a frontier class in circuit complexity). This was recently strengthened by [L. Chen, FOCS 2019, IEEE, Piscataway, NJ, 2019, pp. 1281--1304] to that ${NQP}$ cannot be $(1/2+1/{polylog}(n))$-approximated by polynomial-size ${ACC}^0$ circuits. In this work we will prove that ${NQP}$ cannot be $(1/2+1/n^{\omega(1)})$-approximated by polynomial-size ${ACC}^0$ circuits. As a straightforward application, we obtain an infinitely often nondeterministic pseudorandom generator for polysize ${ACC}^0$ circuits with sub-polynomial seed length. More generally, we establish a connection showing that, for a typical circuit class $\mathscr{C}$, nontrivial deterministic algorithms estimating the acceptance probability of $\mathscr{C}$ circuits imply strong ($1/2 + 1/n^{\omega(1)}$) average-case lower bounds against $\mathscr{C}$ circuits. We also apply this connection to prove new lower bounds against several subclasses of ${\sf TC}^0$ circuits (constant-depth circuits consisting entirely of majority gates), and show that nontrivial derandomization of ${MAJ} \circ {MAJ}$ would imply worst-case lower bounds for ${TC}^0_3$ (${MAJ} \circ{MAJ} \circ {MAJ}$), suggesting that ${TC}^0_3$ lower bounds are probably within reach. Our two new important technical ingredients are (1) techniques from cryptography in ${NC}^0$ [B. Applebaum, Y. Ishai, and E. Kushilevitz, SIAM J. Comput., 36 (2006), pp. 845--888], and (2) probabilistic checkable proofs of proximity with ${NC}^1$-computable proofs.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-02T07:00:00Z
      DOI: 10.1137/20M1364886
       
  • Nearly Optimal Static Las Vegas Succinct Dictionary

    • Free pre-print version: Loading...

      Authors: Huacheng Yu
      Abstract: SIAM 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 a value from $[\sigma]$, the static dictionary problem asks one to preprocess these (key, value) pairs into a data structure, supporting value-retrieval queries: for any given $x\in [U]$, ${valRet}(x)$ must return the value associated with $x$ if $x\in S$, or return $\bot$ if $x\notin S$. The special case where $\sigma=1$ is called the membership problem. The “textbook” solution is to use a hash table, which occupies linear space and answers each query in constant time. On the other hand, the minimum possible space to encode all (key, value) pairs is only ${OPT}:= \lceil\lg_2\binom{U}{n}+n\lg_2 \sigma\rceil$ bits, which could be much smaller than a hash table. In this paper, we design a randomized dictionary data structure using ${OPT}+{poly}\lg n+O(\lg^{(\ell)} U)$ bits of space, and it has expected constant query time, assuming the query algorithm can access an external lookup table of size $n^{\epsilon}$ for any constant $\ell$ and $\epsilon$. The lookup table depends only on $U$, $n$, and $\sigma$, and not the input. Previously, even for membership queries and $U\leq n^{O(1)}$, the best known data structure with constant query time requires ${OPT}+n/{poly}\lg n$ bits of space (Pagh [SIAM J. Comput., 31 (2001), pp. 353--363] and Pǎtraşcu [FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305--313]); the best known using ${OPT}+n^{1-\epsilon}$ space has query time $O(\lg n)$. Our new data structure answers open questions by Pǎtraşcu and Thorup [FOCS, IEEE Computer Society, Los Alamitos, CA, 2008, pp. 305--313; Bull. Eur. Assoc. Theor. Comput. Sci. EATCS, 109 (2013), pp. 7--13]. We also present a scheme that compresses a sequence $X\in[\sigma]^n$ to its zeroth order (empirical) entropy up to $\sigma\cdot{poly}\lg n$ extra bits, supporting decoding each $X_i$ in $O(\lg \sigma)$ expected time.
      Citation: SIAM Journal on Computing
      PubDate: 2022-05-02T07:00:00Z
      DOI: 10.1137/20M1363649
       
  • A Parameterized Approximation Scheme for Min $k$-Cut

    • Free pre-print version: Loading...

      Authors: Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
      Abstract: SIAM 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 to partition the vertex set into $k$ nonempty sets, such that the total weight of the edges with endpoints in different parts is minimized. When $k$ is part of the input, the problem is NP-complete and hard to approximate within any factor less than 2. Recently, the problem has received significant attention from the perspective of parameterized approximation. Gupta, Lee, and Li [Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, A. Czumaj, ed., SIAM, Philadelphia, 2018, pp. 2821--2837] initiated the study of FPT-approximation for the Min $k$-Cut problem and gave a 1.9997-approximation algorithm running in time $2^{\mathcal{O}(k^6)}n^{\mathcal{O}(1)}$. Later, the same set of authors [Proceedings of the 59th IEEE Annual Symposium on Foundations of Computer Science, M. Thorup, ed., 2018, pp. 113--123] designed a $(1 +\epsilon)$-approximation algorithm that runs in time $(k/\epsilon)^{\mathcal{O}(k)}n^{k+\mathcal{O}(1)}$ and a 1.81-approximation algorithm running in time $2^{\mathcal{O}(k^2)}n^{\mathcal{O}(1)}$. More, recently, Kawarabayashi and Lin [Proceedings of the 31st ACM-SIAM Symposium on Discrete Algorithms, S. Chawla, ed., SIAM, Philadelphia, 2020, pp. 990--999] gave a $(5/3 + \epsilon)$-approximation for Min $k$-Cut running in time $2^{\mathcal{O}(k^2 \log k)}n^{\mathcal{O}(1)}$. In this paper, we give a parameterized approximation algorithm with best possible approximation guarantee and best possible running time dependence on said guarantee (up to the exponential time hypothesis and constants in the exponent). In particular, for every $\epsilon> 0$, the algorithm obtains a $(1 +\epsilon)$-approximate solution in time $(k/\epsilon)^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$. The main ingredients of our algorithm are a simple sparsification procedure, a new polynomial time algorithm for decomposing a graph into highly connected parts, and a new exact algorithm with running time $s^{\mathcal{O}(k)}n^{\mathcal{O}(1)}$ on unweighted (multi-) graphs. Here, $s$ denotes the number of edges in a minimum $k$-cut. The latter two are of independent interest.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-25T07:00:00Z
      DOI: 10.1137/20M1383197
       
  • Unit Capacity Maxflow in Almost $m^{4/3}$ Time

    • Free pre-print version: Loading...

      Authors: Tarun Kathuria, Yang P. Liu, Aaron Sidford
      Abstract: SIAM 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 an approximation parameter $\epsilon \in (0, 1)$ computes an additive $\eps mU$-approximate $a$-$b$ maximum flow in time $m^{1+o(1)}/\sqrt{\eps}$. By applying the algorithm for $\eps = (mU)^{-2/3}$, rounding to an integral flow, and using augmenting paths, we obtain an algorithm which computes an exact $a$-$b$ maximum flow in time $m^{4/3+o(1)}U^{1/3}$ and an algorithm which given an $m$-edge bipartite graph computes an exact maximum cardinality matching in time $m^{4/3+o(1)}$.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-18T07:00:00Z
      DOI: 10.1137/20M1383525
       
  • Counting Small Induced Subgraphs Satisfying Monotone Properties

    • Free pre-print version: Loading...

      Authors: Marc Roth, Johannes Schmitt, Philip Wellnitz
      Abstract: SIAM 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 compute the number $\#{\ensuremath{{IndSub}({\Phi,k} \to {G})}}$ of induced subgraphs of size $k$ in $G$ that satisfy $\Phi$. The search for explicit criteria on $\Phi$ ensuring that $\#\ensuremath{{\sc IndSub}}(\Phi)$ is hard was initiated by Jerrum and Meeks [J. Comput. System Sci., 81 (2015), pp. 702--716] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell, and Marx [STOC, ACM, New York, pp. 151--158] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [Discrete Appl. Math., 198 (2016), pp. 170--194] and Dörfler et al. [MFCS, LIPIcs Leibniz Int. Proc. Inform. 138, Wadern Germany, 2019, 26], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is, subgraph-closed, properties: We show that for any nontrivial monotone property $\Phi$, the problem $\#\ensuremath{{\sc IndSub}}(\Phi)$ cannot be solved in time $f(k)\cdot V(G) ^{o(k/ {\log^{1/2}(k)})}$ for any function $f$, unless the exponential time hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a $\#{\ensuremath{{W[1]}}}$-completeness result. The methods we develop for the above problem also allow us to prove a conjecture by Jerrum and Meeks [ACM Trans. Comput. Theory, 7 (2015), 11; Combinatorica 37 (2017), pp. 965--990]: $\#\ensuremath{{\sc IndSub}}(\Phi)$ is $\#{\ensuremath{{W[1]}}}$-complete if $\Phi$ is a nontrivial graph property only depending on the number of edges of the graph.
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-11T07:00:00Z
      DOI: 10.1137/20M1365624
       
  • Separating the Communication Complexity of Truthful and Nontruthful
           Algorithms for Combinatorial Auctions

    • Free pre-print version: Loading...

      Authors: Sepehr Assadi, Hrishikesh Khandeparkar, Raghuvansh R. Saxena, S. Matthew Weinberg
      Abstract: SIAM 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, we prove that any truthful mechanism guaranteeing a $(\nicefrac{3}{4}-\nicefrac{1}{240}+\varepsilon)$-approximation for two buyers with XOS valuations over $m$ items requires $\exp(\Omega(\varepsilon^2 \cdot m))$ communication, whereas a nontruthful algorithm by Dobzinski and Schapira [Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, 2006, pp. 1064--1073] and Feige [SIAM J. Comput., 39 (2009), pp. 122--142] is already known to achieve a $\nicefrac{3}{4}$-approximation in $\mathrm{poly}(m)$ communication. We obtain our separation by proving that any simultaneous protocol (not necessarily truthful) which guarantees a $(\nicefrac{3}{4}-\nicefrac{1}{240}+\varepsilon)$-approximation requires communication $\exp(\Omega(\varepsilon^2 \cdot m))$. The taxation complexity framework of Dobzinski [Proceedings of the $57$th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, 2016, pp. 209--218] extends this lower bound to all truthful mechanisms (including interactive truthful mechanisms).
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-07T07:00:00Z
      DOI: 10.1137/20M1370021
       
  • Smoothing the Gap Between NP and ER

    • Free pre-print version: Loading...

      Authors: Jeff Erickson, Ivor van der Hoog, Tillmann Miltzow
      Abstract: SIAM 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 \ensuremath\exists \mathbbR-complete if it is as hard as the problem existential theory of the reals (ETR) and if it can be written as an ETR formula. Traditionally, these problems are studied in the real random access machine (RAM), a model of computation that assumes that the storage and comparison of real-valued numbers can be done in constant space and time, with infinite precision. The complexity class $\exists \mathbb{R}$ is often called a real RAM analogue of NP, since the problem ETR can be viewed as the real-valued variant of SAT. The real RAM assumption that we can represent and in which we can compare arbitrary irrational values in constant space and time is not very realistic. Yet this assumption is vital, since some $\exists \mathbb{R}$-complete problems have an “exponential bit phenomenon,” where there exists an input for the problem, such that the witness of the solution requires geometric coordinates which need exponential word size when represented in binary. The problems that exhibit this phenomenon are NP-hard (since ETR is NP-hard) but it is unknown if they lie in NP. NP membership is often showed by using the famous Cook--Levin theorem, which states that the existence of a polynomial-time verification algorithm for the problem witness is equivalent to NP membership. The exponential bit phenomenon prohibits a straightforward application of the Cook--Levin theorem. In this paper we first present a result which we believe to be of independent interest: we prove a real RAM analogue to the Cook--Levin theorem which shows that $\exists \mathbb{R}$ membership is equivalent to having a verification algorithm that runs in polynomial-time on a real RAM. This gives an easy proof of \ensuremath\exists \mathbbR-membership, as verification algorithms on a real RAM are much more versatile than ETR formulas. We use this result to construct a framework to study $\exists \mathbb{R}$-complete problems under smoothed analysis. We show that for a wide class of $\exists \mathbb{R}$-complete problems, its witness can be represented with logarithmic input-precision by using smoothed analysis on its real RAM verification algorithm. This shows in a formal way that the boundary between NP and $\exists \mathbb{R}$ (formed by inputs whose solution witness needs high input-precision) consists of contrived input. We apply our framework to well-studied $\exists \mathbb{R}$-complete recognition problems which have the exponential bit phenomenon such as the recognition of realizable order types or the Steinitz problem in fixed dimension. Interestingly our techniques also generalize to problems with a natural notion of resource augmentation (geometric packing, the art gallery problem).
      Citation: SIAM Journal on Computing
      PubDate: 2022-04-07T07:00:00Z
      DOI: 10.1137/20M1385287
       
  • Truly Optimal Euclidean Spanners

    • Free pre-print version: Loading...

      Authors: Hung Le, Shay Solomon
      Abstract: SIAM 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 and early 1990s state that for any $d$-dimensional $n$-point Euclidean space, there exists a $(1+\epsilon)$-spanner with $n \cdot O(\epsilon^{-d+1})$ edges and lightness (normalized weight) $O(\epsilon^{-2d})$. Surprisingly, the fundamental question of whether or not these dependencies on $\epsilon$ and $d$ for small $d$ can be improved has remained elusive, even for $d = 2$. This question naturally arises in any application of Euclidean spanners where precision is a necessity (thus $\epsilon$ is tiny). In the most extreme case $\epsilon$ is inverse polynomial in $n$, and then one could potentially improve the size and lightness bounds by factors that are polynomial in $n$. The state-of-the-art bounds $n \cdot O(\epsilon^{-d+1})$ and $O(\epsilon^{-2d})$ on the size and lightness of spanners are realized by the greedy spanner. In 2016, in a preliminary version, Filtser and Solomon [SIAM J. Comput., 49 (2020), pp. 429--447] proved that, in low-dimensional spaces, the greedy spanner is “near-optimal''; informally, their result states that the greedy spanner for dimension $d$ is just as sparse and light as any other spanner but for dimension larger by a constant factor. Hence the question of whether the greedy spanner is truly optimal remained open to date. The contribution of this paper is twofold: (1) We resolve these longstanding questions by nailing down the dependencies on $\epsilon$ and $d$ and showing that the greedy spanner is truly optimal. Specifically, for any $d= O(1), \epsilon = \Omega({n}^{-\frac{1}{d-1}})$, (a) we show that there are $n$-point sets in $\mathbb{R}^d$ for which any $(1+\epsilon)$-spanner must have $n \cdot \Omega(\epsilon^{-d+1})$ edges, implying that the greedy (and other) spanners achieve the optimal size; (b) we show that there are $n$-point sets in $\mathbb{R}^d$ for which any $(1+\epsilon)$-spanner must have lightness $\Omega(\epsilon^{-d})$, and then improve the upper bound on the lightness of the greedy spanner from $O(\epsilon^{-2d})$ to $O(\epsilon^{-d} \log(\epsilon^{-1}))$. (The lightness upper and lower bounds match up to a lower-order term.) (2) We then complement our negative result for the size of spanners with a rather counterintuitive positive result: Steiner points lead to a quadratic improvement in the size of spanners! Our bound for the size of Steiner spanners in $\mathbb{R}^2$ is tight as well (up to a lower-order term).
      Citation: SIAM Journal on Computing
      PubDate: 2022-03-31T07:00:00Z
      DOI: 10.1137/20M1317906
       
  • Performance of Johnson--Lindenstrauss Transform for $k$-Means and
           $k$-Medians Clustering

    • Free pre-print version: Loading...

      Authors: Konstantin Makarychev, Yury Makarychev, Ilya Razenshteyn
      Abstract: SIAM 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 a factor of $(1+\varepsilon)$ under a projection onto a random $O(\log(k / \varepsilon) / \varepsilon^2)$-dimensional subspace. Further, the cost of every clustering is preserved within $(1+\varepsilon)$. More generally, our result applies to any dimension reduction map satisfying a mild sub-Gaussian-tail condition. Our bound on the dimension is nearly optimal. Additionally, our result applies to Euclidean $k$-clustering with the distances raised to the $p$th power for any constant $p$. For $k$-means, our result resolves an open problem posed by Cohen et al. [STOC 2015, ACM, New York, 2015, pp. 163--172] for $k$-medians, it answers a question raised by Kannan.
      Citation: SIAM Journal on Computing
      PubDate: 2022-03-14T07:00:00Z
      DOI: 10.1137/20M1330701
       
  • Polynomial Data Structure Lower Bounds in the Group Model

    • Free pre-print version: Loading...

      Authors: Alexander Golovnev, Gleb Posobin, Oded Regev, Omri Weinstein
      Abstract: SIAM 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 '80s. We prove a polynomial ($n^{\Omega(1)}$) lower bound for an explicit range counting problem of $n^3$ convex polygons in $\mathbb{R}^2$ (each with $n^{\tilde{O}(1)}$ facets/semialgebraic complexity), against linear storage arithmetic data structures in the group model. Our construction and analysis are based on a combination of techniques in Diophantine approximation, pseudorandomness, and compressed sensing---in particular, on the existence and partial derandomization of optimal binary compressed sensing matrices in the polynomial sparsity regime ($k = n^{1-\delta}$). As a byproduct, this establishes a (logarithmic) separation between compressed sensing matrices and the stronger RIP property.
      Citation: SIAM Journal on Computing
      PubDate: 2022-03-14T07:00:00Z
      DOI: 10.1137/20M1381988
       
  • Efficient Construction of Rigid Matrices Using an NP Oracle

    • Free pre-print version: Loading...

      Authors: Josh Alman, Lijie Chen
      Abstract: SIAM 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 a matrix of rank at most $r$ over $\mathbb{F}$. A central open challenge in complexity theory is to give explicit constructions of rigid matrices for a variety of parameter settings. In this work, building on Williams' seminal connection between circuit-analysis algorithms and lower bounds [J. ACM, 61 (2014), 2], we give a construction of rigid matrices in $P}^{NP}}$. Letting $q = p^r$ be a prime power, we show that there is an absolute constant $\delta>0$ such that, for all constants $\varepsilon>0$, there is a $P}^{NP}}$ machine $M$ such that, for infinitely many $N$'s, $M(1^N)$ outputs a matrix $H_N \in \{0,1\}^{N \times N}$ with $\mathscr{R}_{H_N}(2^{(\log N)^{1/4 - \varepsilon}}) \ge \delta \cdot N^2$ over $\mathbb{F}_q$. Using known connections between matrix rigidity and other topics in complexity theory, we derive several consequences of our constructions, including that there is a function $f \in TIME}[2^{(\log n)^{\omega(1)}}]^{NP}}$ such that $f \notin PH}^{cc}}$. Previously, it was open whether $E}^{NP}} \subset PH}^{cc}}$. For all $\varepsilon>0$, there is a $P}^{NP}}$ machine $M$ such that, for infinitely many $N$'s, $M(1^N)$ outputs an $N \times N$ matrix $H_N \in \{0,1\}^{N \times N}$ whose linear transformation requires depth-2 $\mathbb{F}_q$-linear circuits of size $\Omega(N \cdot 2^{(\log N)^{1/4 - \varepsilon}})$. The previous best lower bound for an explicit family of $N \times N$ matrices over $\mathbb{F}_q$ was only $\Omega(N \log^2 N / (\log\log N)^2)$, for asymptotically good error correcting codes.
      Citation: SIAM Journal on Computing
      PubDate: 2022-03-07T08:00:00Z
      DOI: 10.1137/20M1322297
       
  • The Complexity of Necklace Splitting, Consensus-Halving, and Discrete Ham
           Sandwich

    • Free pre-print version: Loading...

      Authors: Aris Filos-Ratsikas, Paul W. Goldberg
      Abstract: SIAM 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. For NECKLACE SPLITTING, this result is specific to the important special case in which two thieves share the necklace. These are the first PPA-completeness results for problems whose definition does not contain an explicit circuit, thus settling the status of PPA as a class that captures the complexity of such “natural' problems.
      Citation: SIAM Journal on Computing
      PubDate: 2022-02-28T08:00:00Z
      DOI: 10.1137/20M1312678
       
  • Weak Zero-Knowledge beyond the Black-Box Barrier

    • Free pre-print version: Loading...

      Authors: Nir Bitansky, Dakshita Khurana, Omer Paneth
      Abstract: SIAM 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, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Like full-fledged zero- knowledge, protocols satisfying these relaxed notions under standard assumptions have at least four messages. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box. We introduce a new non-black-box technique and use it to obtain the first protocols that cross this barrier under standard assumptions. Our main results are (1) weak zero-knowledge for NP in two messages, assuming quasi-polynomially secure fully homomorphic encryption and other standard primitives (known from quasi-polynomial hardness of learning with errors) as well as subexponentially secure one-way functions; and (2) weak zero-knowledge for NP in three messages under standard polynomial assumptions (following, for example, from fully homomorphic encryption and factoring). We also give, under polynomial assumptions, a two-message witness-hiding protocol for any language L in NP that has a witness encryption scheme. This protocol is also publicly verifiable. Our technique is based on a new homomorphic trapdoor paradigm, which can be seen as a non-black-box analogue of the classic Feige--Lapidot--Shamir trapdoor paradigm.
      Citation: SIAM Journal on Computing
      PubDate: 2022-01-27T08:00:00Z
      DOI: 10.1137/20M1319565
       
  • Equivocating Yao: Constant-Round Adaptively Secure Multiparty Computation
           in the Plain Model

    • Free pre-print version: Loading...

      Authors: Ran Canetti, Oxana Poburinnaya, Muthuramakrishnan Venkitasubramaniam
      Abstract: SIAM Journal on Computing, Ahead of Print.
      Yao's circuit garbling scheme is one of the basic building blocks of cryptographic protocol design. Originally designed to enable two-message, two-party secure computation, the scheme has been extended in many ways and has innumerable applications. Still, a basic question has remained open throughout the years: Can the scheme be extended to guarantee security in the face of an adversary that corrupts both parties, adaptively, as the computation proceeds' We answer this question in the affirmative. We define a new type of symmetric encryption, called functionally equivocal encryption (FEE), and show that when Yao's scheme is implemented with FEE as the underlying encryption mechanism, it becomes secure against such adaptive adversaries. We then show how to implement FEE from any one-way function. Combining our scheme with noncommitting encryption, we obtain the first two-message, two-party computation protocol, and the first constant-round multiparty computation protocol, in the plain model, that are secure against semihonest adversaries who can adaptively corrupt all parties. Using standard techniques, this protocol can be made standalone secure against malicious corruptions in the plain model and universal composability secure in the common random string model. Additional applications include the first fully leakage-tolerant general multiparty computation protocol (with preprocessing), as well as a public-key version of FEE which can serve as a replacement for noncommitting encryption with better efficiency than what is possible for the latter.
      Citation: SIAM Journal on Computing
      PubDate: 2022-01-13T08:00:00Z
      DOI: 10.1137/17M1151602
       
  • Improved Bounds for Perfect Sampling of $k$-Colorings in Graphs

    • Free pre-print version: Loading...

      Authors: Siddharth Bhandari, Sayantan Chakraborty
      Abstract: SIAM 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> 3\Delta$ and returns a random proper $k$-coloring of $G$. The distribution of the coloring is perfectly uniform over the set of all proper $k$-colorings; the expected running time of the algorithm is ${poly}(k,n)=\widetilde{O}(n\Delta^2\cdot \log(k))$. This improves upon a result of Huber [Proceedings of the $30$th ACM Symposium on Theory of Computing (STOC), 1998, pp. 31--40], who obtained a polynomial time perfect sampling algorithm for $k>\Delta^2+2\Delta$. Prior to our work, no algorithm with expected running time ${poly}(k,n)$ was known to guarantee perfectly sampling with a subquadratic number of colors in general. Our algorithm (like several other perfect sampling algorithms including Huber's) is based on the coupling from the past method. Inspired by the bounding chain approach, pioneered independently by Huber (STOC 1998) and Häggström and Nelander [Scand. J. Stat., 26 (1999), pp. 395--411], we employ a novel bounding chain to derive our result for the graph coloring problem.
      Citation: SIAM Journal on Computing
      PubDate: 2022-01-05T08:00:00Z
      DOI: 10.1137/20M1366666
       
 
JournalTOCs
School of Mathematical and Computer Sciences
Heriot-Watt University
Edinburgh, EH14 4AS, UK
Email: journaltocs@hw.ac.uk
Tel: +00 44 (0)131 4513762
 


Your IP address: 34.239.167.149
 
Home (Search)
API
About JournalTOCs
News (blog, publications)
JournalTOCs on Twitter   JournalTOCs on Facebook

JournalTOCs © 2009-