Change search
Refine search result
1 - 29 of 29
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Rows per page
  • 5
  • 10
  • 20
  • 50
  • 100
  • 250
Sort
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
  • Standard (Relevance)
  • Author A-Ö
  • Author Ö-A
  • Title A-Ö
  • Title Ö-A
  • Publication type A-Ö
  • Publication type Ö-A
  • Issued (Oldest first)
  • Issued (Newest first)
  • Created (Oldest first)
  • Created (Newest first)
  • Last updated (Oldest first)
  • Last updated (Newest first)
  • Disputation date (earliest first)
  • Disputation date (latest first)
Select
The maximal number of hits you can export is 250. When you want to export more records please use the Create feeds function.
  • 1.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Balanced Max 2-Sat Might Not be the Hardest: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING2007In: STOC 07: PROCEEDINGS OF THE 39TH ANNUAL ACM SYMPOSIUM ON THEORY OF COMPUTING, New York: ASSOC COMPUTING MACHINERY, , 2007, p. 189-197Conference paper (Refereed)
    Abstract [en]

    We show that, assuming the Unique Games Conjecture, it is NP-hard to approximate MAX 2-SAT within alpha(-)(L)(LZ)+epsilon where 0.9401 < alpha(-)(L)(LZ) < 0.9402 is the believed approximation ratio of the algorithm of Lewin, Livnat and Zwick [28].. This result is surprising considering the fact that balanced instances of MAX 2-SAT, i.e., instances where each variable occurs positively and negatively equally often, can be approximated within 0.9439. In particular, instances in which roughly 68% of the literals are unnegated variables and 32% are negated appear less amenable to approximation than instances where the ratio is 50%-50%.

  • 2.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Conditional Inapproximability and Limited Independence2008Doctoral thesis, monograph (Other scientific)
    Abstract [en]

    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.

  • 3.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    TOWARDS SHARP INAPPROXIMABILITY FOR ANY 2-CSP2010In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 39, no 6, p. 2430-2463Article in journal (Refereed)
    Abstract [en]

    We continue the recent line of work on the connection between semidefinite programming (SDP)-based approximation algorithms and the unique games conjecture. Given any Boolean 2-CSP (or, more generally, any Boolean 2-CSP with real-valued "predicates"), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. Furthermore, we give an SDP-based approximation algorithm and show that the approximation ratio of this algorithm on a certain restricted type of instances is exactly the inapproximability ratio yielded by our hardness result. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that Max 2-AND is unique games-hard to approximate within 0.87435. This improves upon the best previous hardness of alpha(GW) + epsilon approximate to 0.87856 and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of Max 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor aGW and that Max Cut is not the hardest 2-CSP.

  • 4.
    Austrin, Per
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Towards sharp inapproximability for any 2-CSP2007In: 48th Annual IEEE Symposium On Foundations Of Computer Science, Proceedings, 2007, p. 307-317Conference paper (Refereed)
    Abstract [en]

    We continue the recent line, of work on the connection between semidefinite programming-based approximation algorithms and the Unique Games Conjecture. Given any boolean 2-CSP (or more generally, any nonnegative objective function on two boolean variables), we show how to reduce the search for a good inapproximability result to a certain numeric minimization problem. The key objects in our analysis are the vector triples arising when doing clause-by-clause analysis of algorithms based on semidefinite programming. Given a. weighted set of such triples of a certain restricted type, which are "hard" to round in a certain sense, we obtain a Unique Games-based inapproximability matching this "hardness" of rounding the set of vector triples. Conversely, any instance together with an SDP solution can be viewed as a set of vector triples, and we show that we can always find an assignment to the instance which is at least as good as the "hardness" of rounding the corresponding set of vector triples. We conjecture that the restricted type required for the hardness result is in fact no restriction, which would imply that these upper and lower bounds match exactly. This conjecture is supported by all existing results for specific 2-CSPs. As an application, we show that MAX 2-AND is hard to approximate within 0.87435. This improves upon the best previous hardness of alpha(GW) + epsilon approximate to 0.87856, and comes very close to matching the approximation ratio of the best algorithm known, 0.87401. It also establishes that balanced instances of MAX 2-AND, i.e., instances in which each variable occurs positively and negatively equally often, are not the hardest to approximate, as these can be approximated within a factor alpha(GW).

  • 5.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Benabbas, S.
    Georgiou, K.
    Better balance by being biased: A 0.8776-approximation for max bisection2013In: Proc Annu ACM SIAM Symp Discrete Algorithms, 2013, p. 277-294Conference paper (Refereed)
    Abstract [en]

    Recently Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the MAX BISECTION problem. We improve their algorithm to a 0.8776-approximation. As MAX BISECTION is hard to approximate within αGW + ∈ ≈ 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that MAX BISECTION is approximable within αGW -∈, i.e., the bisection constraint (essentially) does not make MAX CUT harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of MAX 2-SAT. Our approximation ratio for this problem exactly matches the optimal approximation ratio for MAX 2-SAT, i.e., αLLZ + ∈ ≈ 0.9401, showing that the bisection constraint does not make MAX 2-SAT harder. This improves on a 0.93-approximation for this problem due to Raghavendra and Tan.

  • 6.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Benabbas, Siavosh
    Georgiou, Konstantinos
    Better Balance by Being Biased: A 0.8776-Approximation for Max Bisection2016In: ACM Transactions on Algorithms, ISSN 1549-6325, E-ISSN 1549-6333, Vol. 13, no 1, article id 2Article in journal (Refereed)
    Abstract [en]

    Recently, Raghavendra and Tan (SODA 2012) gave a 0.85-approximation algorithm for the MAX BISECTION problem. We improve their algorithm to a 0.8776-approximation. As MAX BISECTION is hard to approximate within alpha(GW) + epsilon approximate to 0.8786 under the Unique Games Conjecture (UGC), our algorithm is nearly optimal. We conjecture that MAX BISECTION is approximable within alpha(GW) - epsilon, that is, that the bisection constraint (essentially) does not make MAX CUT harder. We also obtain an optimal algorithm (assuming the UGC) for the analogous variant of MAX 2-SAT. Our approximation ratio for this problem exactly matches the optimal approximation ratio for MAX 2-SAT, that is, alpha(LLZ) + epsilon approximate to 0.9401, showing that the bisection constraint does not make MAX 2-SAT harder. This improves on a 0.93-approximation for this problem from Raghavendra and Tan.

  • 7.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Chung, K. -M
    Mahmoody, M.
    Pass, R.
    Seth, K.
    On the impossibility of cryptography with tamperable randomness2014In: 34rd Annual International Cryptology Conference, CRYPTO 2014, 2014, no PART 1, p. 462-479Conference paper (Refereed)
    Abstract [en]

    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 probability p by a p-tampering attacker.The core of this result is a new Fourier analytic technique 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.

  • 8.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Chung, Kai-Min
    Mahmoody, Mohammad
    Pass, Rafael
    Seth, Karn
    On the Impossibility of Cryptography with Tamperable Randomness2017In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 79, no 4, p. 1052-1101Article in journal (Refereed)
    Abstract [en]

    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.

  • 9.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Chung, Kai-Min
    Mahmoody, Mohammad
    Pass, Rafael
    Seth, Karn
    On the Impossibility of Cryptography with Tamperable Randomness2017In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 79, no 4, p. 1052-1101Article in journal (Refereed)
    Abstract [en]

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

  • 10.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the Usefulness of Predicates2012In: Computing Research Repository, Vol. abs/1204.5662Article in journal (Refereed)
    Abstract [en]

    Motivated by the pervasiveness of strong inapproximability results forMax-CSPs, we introduce a relaxed notion of an approximate solution of aMax-CSP. In this relaxed version, loosely speaking, the algorithm is allowed toreplace the constraints of an instance by some other (possibly real-valued)constraints, and then only needs to satisfy as many of the new constraints aspossible.To be more precise, we introduce the following notion of a predicate $P$being \emph{useful} for a (real-valued) objective $Q$: given an almostsatisfiable Max-$P$ instance, there is an algorithm that beats a randomassignment on the corresponding Max-$Q$ instance applied to the same sets ofliterals. The standard notion of a nontrivial approximation algorithm for aMax-CSP with predicate $P$ is exactly the same as saying that $P$ is useful for$P$ itself.We say that $P$ is useless if it is not useful for any $Q$. This turns out tobe equivalent to the following pseudo-randomness property: given an almostsatisfiable instance of Max-$P$ it is hard to find an assignment such that theinduced distribution on $k$-bit strings defined by the instance is notessentially uniform.Under the Unique Games Conjecture, we give a complete and simplecharacterization of useful Max-CSPs defined by a predicate: such a Max-CSP isuseless if and only if there is a pairwise independent distribution supportedon the satisfying assignments of the predicate. It is natural to also considerthe case when no negations are allowed in the CSP instance, and we derive asimilar complete characterization (under the UGC) there as well.Finally, we also include some results and examples shedding additional lighton the approximability of certain Max-CSPs.

  • 11.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Randomly Supported Independence and Resistance2009In: STOC'09: PROCEEDINGS OF THE 2009 ACM SYMPOSIUM ON THEORY OF COMPUTING, NEW YORK: ASSOC COMPUTING MACHINERY , 2009, p. 483-492Conference paper (Refereed)
    Abstract [en]

    We prove that for any positive integer k, there is a constant C-k such that a randomly selected set of c(k)n(k) log n Boolean vectors with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument, gives the strong-er bound ckn(k). Using a recent, result. by Austrin and Mossel this shows that a predicate on t, bits. Chosen at, random among predicates accepting c(2)t(2) input, vectors, is, assuming the Unique Games Conjecture, likely to be approximation resistant. These result's are close to tight,: we show that there are other constants, c(k)(1), such that a randomly selected set of points is unlikely to support a balanced k-wise. independent distribution and for some c > 0, a random predicate accepting ct(2)/log t input, vectors is is non-trivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the Unique Games Conjecture, any predicate on t bits accepting at least (32/33) - 2(t) inputs is approximation resistant. The results extend front the Boolean domain to larger finite domains.

  • 12.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Univ Toronto, Dept Comp Sci.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Randomly supported independence and resistance2011In: SIAM journal on computing (Print), ISSN 0097-5397, E-ISSN 1095-7111, Vol. 40, no 1, p. 1-27Article in journal (Refereed)
    Abstract [en]

    We prove that for any positive integers q and k there is a constant c(q,k) such that a uniformly random set of c(q,k)n(k) log n vectors in [q](n) with high probability supports a balanced k-wise independent distribution. In the case of k <= 2 a more elaborate argument gives the stronger bound, c(q,k)n(k). Using a recent result by Austrin and Mossel, this shows that a predicate on t bits, chosen at random among predicates accepting c(q,2)t(2) input vectors, is, assuming the unique games conjecture, likely to be approximation resistant. These results are close to tight: we show that there are other constants, c'(q,k), such that a randomly selected set of cardinality c'(q,k)n(k) points is unlikely to support a balanced k-wise independent distribution and, for some c > 0, a random predicate accepting ct(2)/logt input vectors is nontrivially approximable with high probability. In a different application of the result of Austrin and Mossel we prove that, again assuming the unique games conjecture, any predicate on t Boolean inputs accepting at least (32/33).2(t) inputs is approximation resistant. The results extend from balanced distributions to arbitrary product distributions.

  • 13.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Guruswami, V.
    (2 + epsilon)-Sat Is NP-hard2014In: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 2014, p. 1-10Conference paper (Refereed)
    Abstract [en]

    We prove the following hardness result for anatural promise variant of the classical CNF-satisfiabilityproblem: Given a CNF-formula where each clause has widthw and the guarantee that there exists an assignment satisfyingat least g = [w/2]-1 literals in each clause, it is NP-hard tofind a satisfying assignment to the formula (that sets at leastone literal to true in each clause). On the other hand, when g = [w/2], it is easy to find a satisfying assignment via simplegeneralizations of the algorithms for 2-SAT. Viewing 2-SAT σ P as easiness 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 resultshows, for any fixed &amp;epsi; > 0, the hardness of finding a satisfyingassignment to instances of '(2 + &amp;epsi;)-SAT' where the density ofsatisfied literals in each clause is promised 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 edgehas perfect balance (at most k + 1 vertices of either color), itis NP-hard to find a 2-coloring that avoids a monochromaticedge. In other words, a set system with discrepancy 1 is hard todistinguish from a set system with worst possible discrepancy.

  • 14.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Håstad, Johan
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Pass, R.
    On the power of many one-bit provers2013In: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, New York: Association for Computing Machinery (ACM), 2013, p. 215-220Conference paper (Refereed)
    Abstract [en]

    We study the class of languages, denoted by MIP[k, 1-∈, s], which have k-prover games where each prover just sends a single bit, with completeness 1-∈ and soundness error s. For the case that k=1 (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson (Computational Complexity'02) demonstrate that SZK exactly characterizes languages having 1-bit proof systems with "non-trivial" soundness (i.e., 1/2 &lt; s ≤ 1-2∈). We demonstrate that for the case that k ≥ 2, 1-bit k-prover games exhibit a significantly richer structure: •(Folklore) When s ≤ 1/2 k - ∈, MIP[k, 1-∈, s] = BPP; • When 1/2k + ∈ ≤ s &lt; 2/2k -∈, MIP[k, 1-∈, s] = SZK; • When s ≥ 2/2k + ∈, AM ⊆ MIP[k, 1-∈, s]; • For s ≤ 0.62 k/2k and sufficiently large k, MIP[k, 1-∈, s] ⊆ EXP; • For s ≥ 2k/2k, MIP[k, 1, 1-∈, s] = NEXP. As such, 1-bit k-prover games yield a natural "quantitative" approach to relating complexity classes such as BPP, SZK, AM, EXP, and NEXP. We leave open the question of whether a more fine-grained hierarchy (between AM and NEXP) can be established for the case when s ≥ 2/2k + ∈.

  • 15.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS. Aalto Science Institute, Aalto University, Finland .
    Kaski, P.
    Koivisto, M.
    Määttä, J.
    Space-time tradeoffs for subset sum: An improved worst case algorithm2013In: Automata, Languages, and Programming: 40th International Colloquium, ICALP 2013, Riga, Latvia, July 8-12, 2013, Proceedings, Part I, Springer, 2013, no PART 1, p. 45-56Conference paper (Refereed)
    Abstract [en]

    The technique of Schroeppel and Shamir (SICOMP, 1981) has long been the most efficient way to trade space against time for the Subset Sum problem. In the random-instance setting, however, improved tradeoffs exist. In particular, the recently discovered dissection method of Dinur et al. (CRYPTO 2012) yields a significantly improved space-time tradeoff curve for instances with strong randomness properties. Our main result is that these strong randomness assumptions can be removed, obtaining the same space-time tradeoffs in the worst case. We also show that for small space usage the dissection algorithm can be almost fully parallelized. Our strategy for dealing with arbitrary instances is to instead inject the randomness into the dissection process itself by working over a carefully selected but random composite modulus, and to introduce explicit space-time controls into the algorithm by means of a "bailout mechanism".

  • 16.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlof, J.
    Sharper upper bounds for unbalanced Uniquely Decodable Code Pairs2016In: 2016 IEEE International Symposium on Information Theory, Institute of Electrical and Electronics Engineers (IEEE), 2016, Vol. 2016, p. 335-339, article id 7541316Conference paper (Refereed)
    Abstract [en]

    Two sets A, B subset of {0, 1}(n) form a Uniquely Decodable Code Pair (UDCP) if every pair a is an element of A, b is an element of B yields a distinct sum a + b, where the addition is over Z(n). We show that every UDCP A, B, with vertical bar A vertical bar = 2((1-is an element of)n) and vertical bar B vertical bar = 2(beta n), satisfies beta <= 0.4228 + root is an element of. For sufficiently small is an element of, this bound significantly improves previous bounds by Urbanke and Li [Information Theory Workshop '98] and Ordentlich and Shayevitz [2014, arXiv: 1412.8415], which upper bound beta by 0.4921 and 0.4798, respectively, as is an element of approaches 0.

  • 17.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlof, J.
    Subset sum in the absence of concentration2015In: Leibniz International Proceedings in Informatics, LIPIcs, 2015, p. 48-61Conference paper (Refereed)
    Abstract [en]

    We study the exact time complexity of the Subset Sum problem. Our focus is on instances that lack additive structure in the sense that the sums one can form from the subsets of the given integers are not strongly concentrated on any particular integer value. We present a randomized algorithm that runs in O (20.3399nB4) time on instances with the property that no value can arise as a sum of more than B different subsets of the n given integers.

  • 18.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kaski, P.
    Koivisto, M.
    Nederlöf, J.
    Dense Subset Sum may be the hardest2016In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing , 2016Conference paper (Refereed)
    Abstract [en]

    The Subset Sum problem asks whether a given set of n positive integers contains a subset of elements that sum up to a given target t. It is an outstanding open question whether the O∗(2n/2)-time algorithm for Subset Sum by Horowitz and Sahni [J. ACM 1974] can be beaten in the worst-case setting by a "truly faster", O∗(2(0.5-δ)n)-time algorithm, with some constant δ &gt; 0. Continuing an earlier work [STACS 2015], we study Subset Sum parameterized by the maximum bin size β, defined as the largest number of subsets of the n input integers that yield the same sum. For every ∈ &gt; 0 we give a truly faster algorithm for instances with β ≤ 2(0.5-∈)n, as well as instances with β ≥ 20.661n. Consequently, we also obtain a characterization in terms of the popular density parameter n/log2 t: if all instances of density at least 1.003 admit a truly faster algorithm, then so does every instance. This goes against the current intuition that instances of density 1 are the hardest, and therefore is a step toward answering the open question in the affirmative. Our results stem from a novel combinatorial analysis of mixings of earlier algorithms for Subset Sum and a study of an extremal question in additive combinatorics connected to the problem of Uniquely Decodable Code Pairs in information theory.

  • 19.
    Austrin, Per
    et al.
    KTH, School of Electrical Engineering and Computer Science (EECS), Theoretical Computer Science, TCS.
    Kaski, Petteri
    Koivisto, Mikko
    Nederlof, Jesper
    Sharper Upper Bounds for Unbalanced Uniquely Decodable Code Pairs2018In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 64, no 2, p. 1368-1373Article in journal (Refereed)
    Abstract [en]

    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.

  • 20.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, S.
    A characterization of approximation resistance for even k-partite CSPs2013In: ITCS 2013 - Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, New York: Association for Computing Machinery (ACM), 2013, p. 187-196Conference paper (Refereed)
    Abstract [en]

    A constraint satisfaction problem (CSP) is said to be approximation resistant if it is hard to approximate better than the trivial algorithm which picks a uniformly random assignment. Assuming the Unique Games Conjecture, we give a characterization of approximation resistance for k-partite CSPs defined by an even predicate.

  • 21.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, Subhash
    A Simple Deterministic Reduction for the Gap Minimum Distance of Code Problem2014In: IEEE Transactions on Information Theory, ISSN 0018-9448, E-ISSN 1557-9654, Vol. 60, no 10, p. 6636-6645Article in journal (Refereed)
    Abstract [en]

    We present a simple deterministic gap-preserving reduction from SAT to the minimum distance of code problem over F-2. We also show how to extend the reduction to work over any fixed finite field. Previously, a randomized reduction was known due to Dumer, Micciancio, and Sudan, which was recently derandomized by Cheng and Wan. These reductions rely on highly nontrivial coding theoretic constructions, whereas our reduction is elementary. As an additional feature, our reduction gives hardness within a constant factor even for asymptotically good codes, i.e., having constant positive rate and relative distance. Previously, it was not known how to achieve a deterministic reduction for such codes.

  • 22.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, Subhash
    Safra, Muli
    Inapproximability of vertex cover and independent set in bounded degree graphs2011In: Theory of Computing, ISSN 1557-2862, E-ISSN 1557-2862, Vol. 7, p. 27-43Article in journal (Refereed)
  • 23.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Khot, Subhash
    Safra, Muli
    Inapproximability of Vertex Cover and Independent Set in Bounded Degree Graphs2009In: PROCEEDINGS OF THE 24TH ANNUAL IEEE CONFERENCE ON COMPUTATIONAL COMPLEXITY, 2009, p. 74-80Conference paper (Refereed)
    Abstract [en]

    We study the inapproximability of Vertex Cover and Independent Set on degree d graphs. We prove that: Vertex Cover is Unique Games-hard to approximate to within a factor 2 - (2 + O-d (1)) log logd/log d. This exactly matches the algorithmic result of Halperin [1] up to the O-d(1) term. Independent Set is Unique Games-hard to approximate to within a factor O(d/log(2)d). This improves the d/log(O(1)) (d) Unique Games hardness result of Samorodnitsky and Trevisan [2]. Additionally, our result does not rely on the construction of a query efficient PCP as in [2].

  • 24.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Kreitz, Gunnar
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Lower bounds for Subset Cover based Broadcast Encryption2008In: PROGRESS IN CRYPTOLOGY - AFRICACRYPT 2008  , 2008, Vol. 5023, p. 343-356Conference paper (Refereed)
    Abstract [en]

    In this paper, we prove lower bounds for a large class of Subset Cover schemes (including all existing schemes based on pseudo-random sequence generators). In particular, we show that For small r, bandwidth is Omega(r) For some r, bandwidth is Omega(n/log(s)) For large r, bandwidth is n - r where n is the number of users, r is the number of revoked users, and s is the space required per user. These bounds are all tight in the sense that they match known constructions up to small constants.

  • 25.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Manokaran, Rajsekar
    KTH, School of Computer Science and Communication (CSC).
    Wenner, Cenny
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    On the NP-hardness of approximating ordering constraint satisfaction problems2013In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques: 16th International Workshop, APPROX 2013, and 17th International Workshop, RANDOM 2013, Berkeley, CA, USA, August 21-23, 2013. Proceedings, Springer, 2013, p. 26-41Conference paper (Refereed)
    Abstract [en]

    We show improved NP-hardness of approximating Ordering Constraint Satisfaction Problems (OCSPs). For the two most well-studied OCSPs, Maximum Acyclic Subgraph and Maximum Betweenness, we prove inapproximability of 14/15 + ε and 1/2 + ε. An OCSP is said to be approximation resistant if it is hard to approximate better than taking a uniformly random ordering. We prove that the Maximum Non- Betweenness Problem is approximation resistant and that there are width-m 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. Our reductions from Label Cover differ from previous works in two ways. First, we establish a somewhat general bucketing lemma permitting us to reduce the analysis of ordering predicates to that of classical predicates. Second, instead of "folding", which is not available for ordering predicates, we employ permuted instantiations of the predicates to limit the value of poorly correlated strategies.

  • 26.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mossel, Elchanan
    Approximation resistant predicates from pairwise independence2008In: 23rd Annual IEEE Conference on Computational Complexity, proceedings, 2008, p. 249-258Conference paper (Refereed)
    Abstract [en]

    We study the approximability of predicates on k variables from a domain [q], and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate P is approximation resistant if there exists a balanced pairwise independent distribution over [q](k) whose support is contained in the set of satisfying assignments to P. Using constructions of pairwise independent distributions this result implies that For general k >= 3 and q >= 2, the MAX k-CSP(q) problem is UG-hard to approximate within O(kq(2))q(k) + epsilon. For the special case of q = 2, i.e., boolean variables, we can sharpen this bound to (k + O(k(0.525)))/2(k) + epsilon, improving upon the best previous bound of 2k/2(k) + epsilon (Samorodnitsky and Trevisan, STOC'06) by essentially a factor 2. Finally, again for q = 2, assuming that the famous Hadamard Conjecture is true, this can be improved even further and the O(k(0.521)) term can be replaced by the constant 4.

  • 27.
    Austrin, Per
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Mossel, Elchanan
    Approximation resistant predicates from pairwise independence2009In: Computational Complexity, ISSN 1016-3328, E-ISSN 1420-8954, Vol. 18, no 2, p. 249-271Article in journal (Refereed)
    Abstract [en]

    We study the approximability of predicates on k variables from a domain [q], and give a new sufficient condition for such predicates to be approximation resistant under the Unique Games Conjecture. Specifically, we show that a predicate P is approximation resistant if there exists a balanced pairwise independent distribution over [q](k) whose support is contained in the set of satisfying assignments to P. Using constructions of pairwise independent distributions this result implies that For general k >= 3 and q <= 2, the Max k-CSPq problem is UG-hard to approximate within O(kq(2))/q(k) + epsilon. For the special case of q = 2, i.e., boolean variables, we can sharpen this bound to (k + O(k(0.525)))/2(k) + epsilon, improving upon the best previous bound of 2k/2(k) + epsilon (Samorodnitsky and Trevisan, STOC'06) by essentially a factor 2. Finally, again for q = 2, assuming that the famous Hadamard Conjecture is true, this can be improved even further, and the O(k(0.525)) term can be replaced by the constant 4.

  • 28.
    Austrin, Per
    et al.
    University of Toronto.
    O’Donnell, Ryan
    Carnegie Mellon University.
    Wright, John
    Carnegie Mellon University.
    A New Point of NP-Hardness for 2-to-1 Label Cover2012In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2012, p. 1-12Conference paper (Refereed)
    Abstract [en]

    We show that given a satisfiable instance of the 2-to-1 Label Cover problem, it is NP-hard to find a (23/24 + ε)-satisfying assignment

  • 29.
    Austrin, Per
    et al.
    Department of Computer Science, University of Toronto, Canada.
    Pitassi, Toniann
    Department of Computer Science, University of Toronto, Canada.
    Wu, Yu
    Department of Computer Science, University of Toronto, Canada.
    Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems2012In: International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), 2012, p. 13-24Conference paper (Refereed)
    Abstract [en]

    We study the approximability of a number of graph problems: treewidth and pathwidth of graphs, one-shot black (and black-white) pebbling costs of directed acyclic graphs, and a variety of different graph layout problems such as minimum cut linear arrangement and interval graph completion. We show that, assuming the recently introduced Small Set Expansion Conjecture, all of these problems are hard to approximate within any constant factor.

1 - 29 of 29
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf