| 1. |
- Austrin, Per, 1981-
(författare)
-
Conditional Inapproximability and Limited Independence
- 2008
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. These are problems in which we are given a set of constraints, each constraint acting on some k variables, and are asked to find an assignment to the variables satisfyingas many of the constraints as possible. A predicate P : [q]ᵏ → {0, 1} is said to be approximation resistant if it is intractable to approximate the corresponding CSP problem to within a factor which is better than what is expected from a completely random assignment to the variables. We prove that if the Unique Games Conjecture is true, then a sufficient condition for a predicate P :[q]ᵏ → {0, 1} to be approximation resistant is that there exists a pairwise independent distribution over [q]ᵏ which is supported on the set of satisfying assignments Pˉ¹(1) of P. We also study predicates P : {0, 1}² → {0, 1} on two boolean variables. The corresponding CSP problems include fundamental computational problems such as Max Cut and Max 2-Sat. For any P, we give an algorithm and a Unique Games-based hardness result. Under a certain geometric conjecture, the ratios of these two results are shown to match exactly. In addition, this result explains why additional constraints beyond the standard “triangle inequalities” do not appear to help when solving these problems. Furthermore,we are able to use the generic hardness result to obtain improved hardness for the special cases of Max 2-Sat and Max 2-And. For Max 2-Sat, we obtain a hardness of αLLZ + ε ≈ 0.94016, where αLLZ is the approximation ratio of the algorithm due to Lewin, Livnat and Zwick. For Max 2-And, we obtain a hardness of 0.87435. For both of these problems, our results surprisingly demonstrate that the special case of balanced instances (instances where every variable occurs positively and negatively equally often) is not the hardest. Furthermore, the result for Max 2-And also shows that Max Cut is not the hardest 2-CSP. Motivated by the result for k-CSP problems, and their fundamental importance in computer science in general, we then study t-wise independent distributions with random support. We prove that, with high probability, poly(q) ・ n² random points in [q]ⁿ can support a pairwise independent distribution. Then, again with high probability, we show that (poly(q) ・n)ᵗ log(nᵗ) random points in [q]ⁿ can support a t-wise independent distribution. For constant t and q, we show that Ω(nᵗ) random points are necessary in order to be able to support a t-wise independent balanced distribution with non-negligible probability. Also, we show that every subset of [q]ⁿ with size at least qⁿ(1−poly(q)ˉᵗ) can support a t-wise independent distribution. Finally, we prove a certain noise correlation bound for low-degree functions with small Fourier coefficients. This type of result is generally useful in hardness of approximation, derandomization, and additive combinatorics.
|
|
| 2. |
- Austrin, Per, 1981-, et al.
(författare)
-
Global cardinality constraints make approximating some MAx-2-CSPS harder
- 2019
-
Ingår i: Leibniz International Proceedings in Informatics, LIPIcs. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. - 9783959771252
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 3. |
- Austrin, Per, 1981-, et al.
(författare)
-
Improved Inapproximability of Rainbow Coloring
- 2020
-
Ingår i: Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SODA 2020. - Philadelphia, PA : Society for Industrial & Applied Mathematics (SIAM). ; , s. 1479-1495
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 4. |
- Austrin, Per, 1981-, et al.
(författare)
-
On the Impossibility of Cryptography with Tamperable Randomness
- 2017
-
Ingår i: Algorithmica. - : SPRINGER. - 0178-4617 .- 1432-0541. ; 79:4, s. 1052-1101
-
Tidskriftsartikel (refereegranskat)abstract
- We initiate a study of the security of cryptographic primitives in the presence of efficient tampering attacks to the randomness of honest parties. More precisely, we consider p-tampering attackers that may efficiently tamper with each bit of the honest parties' random tape with probability p, but have to do so in an "online" fashion. Our main result is a strong negative result: We show that any secure encryption scheme, bit commitment scheme, or zero-knowledge protocol can be "broken" with advantage Omega(p) by a p-tampering attacker. The core of this result is a new algorithm for biasing the output of bounded-value functions, which may be of independent interest. We also show that this result cannot be extended to primitives such as signature schemes and identification protocols: assuming the existence of one-way functions, such primitives can be made resilient to (1/poly(n))-tampering attacks where n is the security parameter.
|
|
| 5. |
- Austrin, Per, 1981-, et al.
(författare)
-
On the Impossibility of Key Agreements from Quantum Random Oracles
- 2022
-
Ingår i: Advances In Cryptology - CRYPTO 2022, PT II. - Cham : Springer Nature. ; , s. 165-194
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 6. |
- Austrin, Per, 1981-, et al.
(författare)
-
On the NP-hardness of approximating ordering-constraint satisfaction problems
- 2015
-
Ingår i: Theory of Computing. - : Theory of Computing Exchange. - 1557-2862. ; 11, s. 257-283
-
Tidskriftsartikel (refereegranskat)abstract
- We show improved NPNP-hardness of approximating Ordering-Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove NPNP-hard approximation factors of 14/15+ε14/15+ε and 1/2+ε1/2+ε. When it is hard to approximate an OCSP by a constant better than taking a uniformly-at-random ordering, then the OCSP is said to be approximation resistant. We show that the Maximum Non-Betweenness Problem is approximation resistant and that there are width-mm approximation-resistant OCSPs accepting only a fraction 1/(m/2)! of assignments. These results provide the first examples of approximation-resistant OCSPs subject only to P≠NP.
|
|
| 7. |
- Austrin, Per, 1981-, et al.
(författare)
-
Optimal inapproximability with universal factor graphs
- 2021
-
Ingår i: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. - Philadelphia, PA : Association for Computing Machinery. ; , s. 434-453
-
Konferensbidrag (refereegranskat)abstract
- 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”.
|
|
| 8. |
- Austrin, Per, 1981-, et al.
(författare)
-
Perfect Matching in Random Graphs is as Hard as Tseitin
- 2022
-
Ingår i: Proceedings of the 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). - : Association for Computing Machinery (ACM). ; , s. 979-1012
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
| 9. |
- Austrin, Per, 1981-, et al.
(författare)
-
Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs
- 2018
-
Ingår i: IEEE Transactions on Information Theory. - : IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC. - 0018-9448 .- 1557-9654. ; 64:2, s. 1368-1373
-
Tidskriftsartikel (refereegranskat)abstract
- 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.
|
|
| 10. |
- Austrin, Per, 1981-, et al.
(författare)
-
Sum-Of-Squares Lower Bounds for the Minimum Circuit Size Problem
- 2023
-
Ingår i: 38th Computational Complexity Conference, CCC 2023. - : Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing.
-
Konferensbidrag (refereegranskat)abstract
- 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.
|
|
