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 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.

Assuming the Unique Games Conjecture, we show that existing approximation algorithms for some Boolean Max-2-CSPs with cardinality constraints are optimal. In particular, we prove that Max-Cut with cardinality constraints is UG-hard to approximate within ≈ 0.858, and that Max-2-Sat with cardinality constraints is UG-hard to approximate within ≈ 0.929. In both cases, the previous best hardness results were the same as the hardness of the corresponding unconstrained Max-2-CSP (≈ 0.878 for Max-Cut, and ≈ 0.940 for Max-2-Sat). The hardness for Max-2-Sat applies to monotone Max-2-Sat instances, meaning that we also obtain tight inapproximability for the Max-k-Vertex-Cover problem.

We study tensor networks as a model of arithmetic computation for evaluating multilinear maps. These capture any algorithm based on low border rank tensor decompositions, such as O(nω+ϵ) time matrix multiplication, and in addition many other algorithms such as O(nlog n) 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 border 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: (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 Ω(nd2v/3e) 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 permanent of an n × n matrix.

Two sets of 0-1 vectors of fixed length form a uniquely decodeable code pair if their Cartesian product is of the same size as their sumset, where the addition is pointwise over integers. For the size of the sumset of such a pair, van Tilborg has given an upper bound in the general case. Urbanke and Li, and later Ordentlich and Shayevitz, have given better bounds in the unbalanced case, that is, when either of the two sets is sufficiently large. Improvements to the latter bounds are presented.

We prove the following hardness result for a natural promise variant of the classical CNF-satisfiability problem: Given a CNF-formula where each clause has width w and the guarantee that there exists an assignment satisfying at least g = [w/2]-1 literals in each clause, it is NP-hard to find a satisfying assignment to the formula (that sets at least one literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simple generalizations of the algorithms for 2-Sat. Viewing 2-Sat 2 P as tractability of Sat when 1 in 2 literals are true in every clause, and NP-hardness of 3-Sat as intractability of Sat when 1 in 3 literals are true, our result shows, for any fixed ϵ > 0, the difficulty of finding a satisfying assignment to instances of "(2 + ϵ)-Sat" where the density of satisfied literals in each clause is guaranteed to exceed 1/2+ϵ. We also strengthen the results to prove that, given a (2k +1)-uniform hypergraph that can be 2-colored such that each edge has perfect balance (at most k +1 vertices of either color), it is NP-hard to find a 2-coloring that avoids a monochromatic edge. In other words, a set system with discrepancy 1 is hard to distinguish from a set system with worst possible discrepancy. Finally, we prove a general result showing the intractability of promise constraint satisfaction problems based on the paucity of certain "weak polymorphisms." The core of the above hardness results is the claim that the only weak polymorphisms in these particular cases are juntas depending on few variables.