A Boolean predicate A is defined to be promise-useful if PCSP(A,B) is tractable for some nontrivial Boolean predicate B and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming P ≠ NP). While we do not obtain a complete characterization, our conditions are sufficient to classify all predicates of arity at most 4 and almost all predicates of arity 5. We also derive asymptotic results to show that for large arities a vast majority of all predicates are promise-useless. Our results are primarily obtained by a thorough study of the “Promise-SAT” problem, in which we are given a k-SAT instance with the promise that there is a satisfying assignment for which the literal values of each clause satisfy some additional constraint. The algorithmic results are based on the basic LP + affine IP algorithm of Brakensiek et al. (SICOMP, 2020) while we use a number of novel criteria to establish NP-hardness.

Given a k-CNF formula and an integer s ≥ 2, we study algorithms that obtain s solutions to the formula that are as dispersed as possible. For s = 2, this problem of computing the diameter of a k-CNF formula was initiated by Creszenzi and Rossi, who showed strong hardness results even for k = 2. The current best upper bound [Angelsmark and Thapper ’04] goes to 4 n as k → ∞. As our first result, we show that this quadratic blow up is not necessary by utilizing the Fast-Fourier transform (FFT) to give a O ∗ (2n ) time exact algorithm for computing the diameter of any k-CNF formula. For s > 2, the problem was raised in the SAT community (Nadel ’11) and several heuristics have been proposed for it, but no algorithms with theoretical guarantees are known. We give exact algorithms using FFT and clique-finding that run in O ∗ (2(s−1)n ) and O ∗ (s 2 |ΩF| ω⌈s/3⌉ ) respectively, where |ΩF| is the size of the solutions space of the formula F and ω is the matrix multiplication exponent. However, current SAT algorithms for finding one solution run in time O ∗ (2εkn ) for εk ≈ 1−Θ(1/k), which is much faster than all above run times. As our main result, we analyze two popular SAT algorithms - PPZ (Paturi, Pudlák, Zane ’97) and Schöning’s (’02) algorithms, and show that in time poly(s)O ∗ (2εkn ), they can be used to approximate diameter as well as the dispersion (s > 2) problem. While we need to modify Schöning’s original algorithm for technical reasons, we show that the PPZ algorithm, without any modification, samples solutions in a geometric sense. We believe this geometric sampling property of PPZ may be of independent interest. Finally, we focus on diverse solutions to NP-complete optimization problems, and give biapproximations running in time poly(s)O ∗ (2εn) with ε < 1 for several problems such as Maximum Independent Set, Minimum Vertex Cover, Minimum Hitting Set, Feedback Vertex Set, Multicut on Trees and Interval Vertex Deletion. For all of these problems, all existing exact methods for finding optimal diverse solutions have a runtime with at least an exponential dependence on the number of solutions s. Our methods show that by relaxing to bi-approximations, this dependence on s can be made polynomial.

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: (1) Optimal inapproximability for Max-3-Lin and Max-3-Sat (H & aring;stad, J. ACM 2001). (2) Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). (3) Hardness of the "(2 + epsilon)-Sat" problem and other Promise CSPs (Austrin et al., SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call "functional folding".

We prove lower bounds for the Minimum Circuit Size Problem (MCSP) in the Sum-of-Squares (SoS) proof system. Our main result is that for every Boolean function f : (0, 1)n → (0, 1), SoS requires degree Ω(s1−ϵ) to prove that f does not have circuits of size s (for any s > poly(n)). As a corollary we obtain that there are no low degree SoS proofs of the statement NP ⊈ P/poly. We also show that for any 0 < α < 1 there are Boolean functions with circuit complexity larger than 2nα but SoS requires size 22Ω(nα) to prove this. In addition we prove analogous results on the minimum monotone circuit size for monotone Boolean slice functions. Our approach is quite general. Namely, we show that if a proof system Q has strong enough constraint satisfaction problem lower bounds that only depend on good expansion of the constraint-variable incidence graph and, furthermore, Q is expressive enough that variables can be substituted by local Boolean functions, then the MCSP problem is hard for Q.

We study the following question, first publicly posed by Hosoyamada and Yamakawa in 2018. Can parties A, B with quantum computing power and classical communication rely only on a random oracle (that can be queried in quantum superposition) to agree on a key that is private from eavesdroppers? We make the first progress on the question above and prove the following. - When only one of the parties A is classical and the other party B is quantum powered, as long as they ask a total of d oracle queries and agree on a key with probability 1, then there is always a way to break the key agreement by asking O(d(2)) number of classical oracle queries. - When both parties can make quantum queries to the random oracle, we introduce a natural conjecture, which if true would imply attacks with poly(d) classical queries to the random oracle. Our conjecture, roughly speaking, states that the multiplication of any two degree-d real-valued polynomials over the Boolean hypercube of influence at most delta = 1/poly (d) is nonzero. We then prove our conjecture for exponentially small influences, which leads to an (unconditional) classical 2(O(md))-query attack on any such key agreement protocol, where m is the oracle's output length. - Since our attacks are classical, we then ask whether it is always possible to find classical attacks on key agreements with imperfect completeness in the quantum random oracle model. We prove a barrier for this approach, by showing that if the folklore "Simulation Conjecture" (first formally stated by Aaronson and Ambainis in 2009) about the possibility of simulating efficient-query quantum algorithms using efficient-query classical algorithms is false, then there is in fact such a secure key agreement in the quantum random oracle model that cannot be broken classically.

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree (n= log n) in the Polynomial Calculus (over fields of characteristic 6= 2) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovasz-Schrijver proof system requires nrounds to refute these formulas for some > 0. The results are obtained by a worst-case to averagecase reduction of these formulas relying on a topological embedding theorem which may be of independent interest.

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree Ω(n/logn) in the Polynomial Calculus (over fields of characteristic ≠2) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovász-Schrijver proof system requires nδ rounds to refute these formulas for some δ>0. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.

We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. hese capture any algorithm based on low-rank tensor decompositions, such as O(nω+ϵ) time matrix multiplication, and in addition many other algorithms such as O(nlogn) time discrete Fourier transform and O∗(2n) time for computing the permanent of a matrix. However, tensor networks sometimes yield faster algorithms than those that follow from low-rank decompositions. For instance the fastest known O(n(ω+ϵ)t) time algorithms for counting 3t-cliques can be implemented with tensor networks, even though the underlying tensor has rank n3t for all t≥2. For counting homomorphisms of a general pattern graph P into a host graph on n vertices we obtain an upper bound of O(n(ω+ϵ)bw(P)/2) where bw(P) is the branchwidth of P. This essentially matches the bound for counting cliques, and yields small improvements over previous algorithms for many choices of P. While powerful, the model still has limitations, and we are able to show a number of unconditional lower bounds for various multilinear maps, including the following. [(a)] An Ω(nbw(P)) time lower bound for counting homomorphisms from P to an n-vertex graph, matching the upper bound if ω=2. In particular for P a v-clique this yields an Ω(n⌈2v/3⌉) time lower bound for counting v-cliques, and for P a k-uniform v-hyperclique we obtain an Ω(nv) time lower bound for k ≥ 3, ruling out tensor networks as an approach to obtaining non-trivial algorithms for hyperclique counting and the Max-3-CSP problem. [(b)] An Ω(20.918n) time lower bound for the determinant and the permanent of an n×n matrix.

The factor graph of an instance of a constraint satisfaction problem (CSP) is the bipartite graph indicating which variables appear in each constraint. An instance of the CSP is given by the factor graph together with a list of which predicate is applied for each constraint. We establish that many Max-CSPs remain as hard to approximate as in the general case even when the factor graph is fixed (depending only on the size of the instance) and known in advance. Examples of results obtained for this restricted setting are: 1. Optimal inapproximability for Max-3-Lin and Max-3-Sat (Håstad, J. ACM 2001). 2. Approximation resistance for predicates supporting pairwise independent subgroups (Chan, J. ACM 2016). 3. Hardness of the “(2 + ε)-Sat” problem and other Promise CSPs (Austrin et al., SIAM J. Comput. 2017). The main technical tool used to establish these results is a new way of folding the long code which we call “functional folding”.

A rainbow q-coloring of a k-uniform hypergraph is a q-coloring of the vertex set such that every hyperedge contains all q colors. We prove that given a rainbow (k - 2left perpendicular root kright perpendicular)-colorable k-uniform hypergraph, it is NP-hard to find a normal 2-coloring. Previously, this was only known for rainbow left perpendiculark/2right perpendicular-colorable hypergraphs (Guruswami and Lee, SODA 2015). We also study a generalization which we call rainbow (q; p)-coloring, defined as a coloring using q colors such that every hyperedge contains at least p colors. We prove that given a rainbow (k - left perpendicular root kcright perpendicular; k - left perpendicular3 root kcright perpendicular)-colorable k uniform hypergraph, it is NP-hard to find a normal c-coloring for any c = o(k). The proof of our second result relies on two combinatorial theorems. One of the theorems was proved by Sarkaria (J. Comb. Theory, Ser. B 1990) using topological methods and the other theorem we prove using a generalized BorsukUlam theorem.