kth.sePublications
Change search
Refine search result
1 - 10 of 10
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • 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. Cai, Jin-Yi
    et al.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Lu, Pinyan
    From Holant to #CSP and Back: Dichotomy for Holant (c) Problems2012In: Algorithmica, ISSN 0178-4617, E-ISSN 1432-0541, Vol. 64, no 3, p. 511-533Article in journal (Refereed)
    Abstract [en]

    We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain a",. We prove three complexity dichotomy theorems, leading to a general theorem for Holant (c) problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on G=(V,E) over a set of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to F , of Sigma Pi f(v)(sigma vertical bar E(v)), sigma:E ->{0,1}v epsilon V where f(v) epsilon F boolean OR {0, 1} (0, 1 are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy can be only naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on Boolean complex weighted #CSP.

  • 2.
    Cai, Jin-Yi
    et al.
    University of Wisconsin - Madison.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Lu, Pinyan
    Microsoft Research Asia.
    From Holant to #CSP and Back: Dichotomy for Holantc Problems2010In: Algorithms and Computation - 21st International Symposium / [ed] Otfried Cheong and Kyung-Yong Chwa and Kunsoo Park, Springer , 2010, p. 253-265Conference paper (Refereed)
    Abstract [en]

    We explore the intricate interdependent relationship among counting problems, considered from three frameworks for such problems: Holant Problems, counting CSP and weighted H-colorings. We consider these problems for general complex valued functions that take Boolean inputs. We show that results from one framework can be used to derive results in another, and this happens in both directions. Holographic reductions discover an underlying unity, which is only revealed when these counting problems are investigated in the complex domain ℂ. We prove three complexity dichotomy theorems, leading to a general theorem for Holant c problems. This is the natural class of Holant problems where one can assign constants 0 or 1. More specifically, given any signature grid on G = (V,E) over a set ℱ of symmetric functions, we completely classify the complexity to be in P or #P-hard, according to ℱ, of∑σ:E→{0,1}∏v∈Vfv(σ∣E(v)),∑σ:E→{0,1}∏v∈Vfv(σ∣E(v)),where f v  ∈ ℱ ∪{{\bf 0}, {\bf 1}}∪{{\bf 0}, {\bf 1}} (0, 1 are the unary constant 0, 1 functions). Not only is holographic reduction the main tool, but also the final dichotomy is naturally stated in the language of holographic transformations. The proof goes through another dichotomy theorem on Boolean complex weighted #CSP.

    Download full text (pdf)
    fulltext
  • 3.
    Guo, Heng
    et al.
    University of Wisconsin - Madison.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Lu, Pinyan
    Microsoft Research Asia.
    Xia, Mingji
    Chinese Acad Sci, Inst Software, Beijing 100190, Peoples R China.
    The Complexity of Weighted Boolean #CSP Modulo k2011In: 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011 / [ed] Thomas Schwentick and Christoph Dürr, Dagstuhl, Germany: Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik , 2011, p. 249-260Conference paper (Refereed)
    Abstract [en]

    We prove a complexity dichotomy theorem for counting weighted Boolean CSP modulo k  for any positive integer k1 . This generalizes a theorem by Faben for the unweighted setting. In the weighted setting, there are new interesting tractable problems. We first prove a dichotomy theorem for the finite field case where k  is a prime. It turns out that the dichotomy theorem for the finite field is very similar to the one for the complex weighted Boolean #CSP, found by [Cai, Lu and Xia, STOC 2009]. Then we further extend the result to an arbitrary integer k .

    Download full text (pdf)
    fulltext
  • 4.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity2012Report (Other academic)
    Abstract [en]

    In this paper, we study the approximability of Max CSP(P) where P is a Boolean predicate. We prove that assuming Khot’s d-to-1 Conjecture, if the set of accepting inputs of P strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate MaxCSP(P) better than the simple random assignment algorithm even on satisfiable instances.This is a generalization of a work by O’Donnell and Wu which proved that it is NP-hard to approximate satisfiable instances of Max CSP(NTW) beyond 5/8 + epsilon for any epsilon > 0 based on Khot’s d-to-1 Conjecture, where NTW is the “Not Two” predicate of size 3.

    Download full text (pdf)
    tr12-040
  • 5.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Approximation resistance on satisfiable instances for predicates with few accepting inputs2013In: Symposium on Theory of Computing Conference / [ed] Dan Boneh, Tim Roughgarden, Joan Feigenbaum, 2013, p. 457-466Conference paper (Refereed)
    Abstract [en]

     For every integer k≥ 3, we prove that there is a predicate P on k Boolean variables with 2O(k1/3) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Hastad and Khot where the predicate has 2 O(k1/2) accepting assignments.

    Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Chan [5]. We also use techniques from Wenner [32] to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture.

    Download full text (pdf)
    stoc13
  • 6.
    Huang, Sangxia
    KTH, School of Electrical Engineering and Computer Science (EECS), Computer Science, Theoretical Computer Science, TCS.
    Approximation resistance on satisfiable instances for predicates with few accepting inputs2014In: Theory of Computing, E-ISSN 1557-2862, Vol. 10, p. 359-388Article in journal (Refereed)
    Abstract [en]

    For every integer k ≥ 3, we prove that there is a predicate P on k Boolean variables with (Formula Presented) accepting assignments that is approximation resistant even on satisfiable instances. That is, given a satisfiable CSP instance with constraint P, we cannot achieve better approximation ratio than simply picking random assignments. This improves the best previously known result by Håstad and Khot (Theory of Computing, 2005) who showed that a predicate on k variables with 2O(k1/2) accepting assignments is approximation resistant on satisfiable instances. Our construction is inspired by several recent developments. One is the idea of using direct sums to improve soundness of PCPs, developed by Siu On Chan (STOC, 2013). We also use techniques from Cenny Wenner (Theory of Computing, 2013) to construct PCPs with perfect completeness without relying on the d-to-1 Conjecture. 

  • 7.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Hardness of Constraint Satisfaction and Hypergraph Coloring: Constructions of Probabilistically Checkable Proofs with Perfect Completeness2015Doctoral thesis, monograph (Other academic)
    Abstract [en]

    A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. This landmark theorem, and the works leading up to it, laid the foundation for many subsequent works in computational complexity theory, the most prominent among them being the study of inapproximability of combinatorial optimization problems.

    This thesis focuses on a broad class of combinatorial optimization problems called Constraint Satisfaction Problems (CSPs). In an instance of a CSP problem of arity k, we are given a set of variables taking values from some finite domain, and a set of constraints each involving a subset of at most k variables. The goal is to find an assignment that simultaneously satisfies as many constraints as possible. An alternative formulation of the goal that is commonly used is Gap-CSP, where the goal is to decide whether a CSP instance is satisfiable or far from satisfiable, where the exact meaning of being far from satisfiable varies depending on the problems.We first study Boolean CSPs, where the domain of the variables is {0,1}. The main question we study is the hardness of distinguishing satisfiable Boolean CSP instances from those for which no assignment satisfies more than some epsilon fraction of the constraints. Intuitively, as the arity increases, the CSP gets more complex and thus the hardness parameter epsilon should decrease. We show that for Boolean CSPs of arity k, it is NP-hard to distinguish satisfiable instances from those that are at most 2^{~O(k^{1/3})}/2^k-satisfiable.

    We also study coloring of graphs and hypergraphs. Given a graph or a hypergraph, a coloring is an assignment of colors to vertices, such that all edges or hyperedges are non-monochromatic. The gap problem is to distinguish instances that are colorable with a small number of colors, from those that require a large number of colors. For graphs, we prove that there exists a constant K_0>0, such that for any K >= K_0, it is NP-hard to distinguish K-colorable graphs from those that require 2^{Omega(K^{1/3})} colors. For hypergraphs, we prove that it is quasi-NP-hard to distinguish 2-colorable 8-uniform hypergraphs of size N from those that require 2^{(log N)^{1/4-o(1)}} colors.

    In terms of techniques, all these results are based on constructions of PCPs with perfect completeness, that is, PCPs where the probabilistic proof verification procedure always accepts a correct proof. Not only is this a very natural property for proofs, but it can also be an essential requirement in many applications. It has always been particularly challenging to construct PCPs with perfect completeness for NP statements due to limitations in techniques. Our improved hardness results build on and extend many of the current approaches. Our Boolean CSP result and GraphColoring result were proved by adapting the Direct Sum of PCPs idea by Siu On Chan to the perfect completeness setting. Our proof for hypergraph coloring hardness improves and simplifies the recent work by Khot and Saket, in which they proposed the notion of superposition complexity of CSPs.

    Download full text (pdf)
    Thesis
    Download (pdf)
    Errata
  • 8.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Improved Hardness of Approximating Chromatic Number2013In: 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 / [ed] Prasad Raghavendra, Sofya Raskhodnikova, Klaus Jansen, José D. P. Rolim, Springer, 2013, p. 233-243Conference paper (Refereed)
    Abstract [en]

    We prove that for sufficiently large K, it is NP-hard to color K-colorable graphs with less than 2Ω(K 1/3) colors. This improves the previous result of K versus K1/25 log K in Khot [1].

    Download full text (pdf)
    approx13
  • 9.
    Huang, Sangxia
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Lu, Pinyan
    A Dichotomy for Real Weighted Holant Problems2012In: 2012 IEEE 27th Annual Conference On Computational Complexity (CCC), IEEE , 2012, p. 96-106Conference paper (Refereed)
    Abstract [en]

    Holant is a framework of counting characterized by local constraints. It is closely related to other well-studied frameworks such as #CSP and Graph Homomorphism. An effective dichotomy for such frameworks can immediately settle the complexity of all combinatorial problems expressible in that framework. Both #CSP and Graph Homomorphism can be viewed as sub-families of Holant with the additional assumption that the equality constraints are always available. Other subfamilies of Holant such as Holant* and Holant(c) problems, in which we assume some specific sets of constraints to be freely available, were also studied. The Holant framework becomes more expressive and contains more interesting tractable cases with less or no freely available constraint functions, while, on the other hand, it also becomes more challenging to obtain a complete characterization of its time complexity. Recently, complexity dichotomy for a variety of sub-families of Holant such as #CSP, Graph Homomorphism, Holant* and Holant(c) were proved. The dichotomy for the general Holant framework, which is the most desirable, still remains open. In this paper, we prove a dichotomy for the general Holant framework where all the constraints are real symmetric functions. This setting already captures most of the interesting combinatorial problems defined by local constraints, such as (perfect) matching, independent set, vertex cover and so on. This is the first time a dichotomy is obtained for general Holant Problems without any auxiliary functions. One benefit of working with Holant framework is some powerful new reduction techniques such as Holographic reduction. Along the proof of our dichotomy, we introduce a new reduction technique, namely realizing a constraint function by approximating it. This new technique is employed in our proof in a situation where it seems that all previous reduction techniques fail, thus this new idea of reduction might also be of independent interest. Besides proving dichotomy and developing new technique, we also obtained some interesting by-products. We prove a dichotomy for #CSP restricting to instances where each variable appears a multiple of d times for any d. We also prove that counting the number of Eulerian-Orientations on 2k-regular graphs is #P-hard for any k >= 2.

  • 10.
    Håstad, Johan
    et al.
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Huang, Sangxia
    KTH, School of Computer Science and Communication (CSC), Theoretical Computer Science, TCS.
    Manokaran, R.
    O’Donnell, R.
    Wright, J.
    Improved NP-inapproximability for 2-variable linear equations2015In: Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH , 2015, Vol. 40, p. 341-360Conference paper (Refereed)
    Abstract [en]

    An instance of the 2-Lin(2) problem is a system of equations of the form "xi + xj = b (mod 2)". Given such a system in which it’s possible to satisfy all but an C ε fraction of the equations, we show it is NP-hard to satisfy all but a Cε fraction of the equations, for any C < 11/8 = 1.375 (and any 0 < ε ≤ 1/8). The previous best result, standing for over 15 years, had 5/4 in place of 11/8. Our result provides the best known NP-hardness even for the Unique-Games problem, and it also holds for the special case of Max-Cut. The precise factor 11 8 is unlikely to be best possible; we also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2. Our proof is by a modified gadget reduction from a pairwise-independent predicate. We also show an inherent limitation to this type of gadget reduction. In particular, any such reduction can never establish a hardness factor C greater than 2.54. Previously, no such limitation on gadget reductions was known.

1 - 10 of 10
CiteExportLink to result list
Permanent link
Cite
Citation style
  • apa
  • 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