Search Results

Documents authored by Huang, Neng

Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.28
Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP

Authors: Suprovat Ghoshal, Neng Huang, Euiwoong Lee, Konstantin Makarychev, and Yury Makarychev

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
We describe an Ω̃(1/d⁴)-improvement over threshold rounding schemes for a broad class of Boolean MAX 2-CSP instances in which every variable appears in at most d constraints. In the case of MAX 2-SAT, we improve the ratio further and obtain an (β_⋆ + Ω̃(1/d²))-factor approximation algorithm for bounded-degree MAX 2-SAT instances, where β_⋆ is the UGC-optimal approximation ratio for MAX 2-SAT achieved by the LLZ algorithm [Lewin et al., 2002]. Our result generalizes an (α_GW + Ω̃(1/d²))-factor approximation algorithm for MAX CUT on graphs with degrees bounded by d, due to Hsieh and Kothari [Hsieh and Kothari, 2023]. Together with the state-of-the-art approximability results for MAX DI-CUT and MAX 2-AND [Brakensiek et al., 2023], our result suggests that similar improvements exist for bounded-degree instances of these problems as well.
Cite as

Suprovat Ghoshal, Neng Huang, Euiwoong Lee, Konstantin Makarychev, and Yury Makarychev. Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 28:1-28:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{ghoshal_et_al:LIPIcs.APPROX/RANDOM.2026.28,
  author =	{Ghoshal, Suprovat and Huang, Neng and Lee, Euiwoong and Makarychev, Konstantin and Makarychev, Yury},
  title =	{{Threshold Rounding and Bounded-Degree Boolean MAX 2-CSP}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{28:1--28:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.28},
  URN =		{urn:nbn:de:0030-drops-277451},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.28},
  annote =	{Keywords: MAX 2-SAT, Approximation Algorithms, Constraint Satisfaction Problems}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2026.78
Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs

Authors: Antares Chen, Neng Huang, and Kunal Marwaha

Published in: LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)

Abstract
We construct and analyze a message-passing algorithm for random constraint satisfaction problems (CSPs) at large clause density, generalizing work of El Alaoui, Montanari, and Sellke for Maximum Cut [Alaoui et al., 2023] through a connection between random CSPs and mean-field Ising spin glasses [Alaoui et al., 2021; Jones et al., 2023]. For CSPs with even predicates, the algorithm asymptotically solves a stochastic optimal control problem dual to an extended Parisi variational principle. This gives an optimal fraction of satisfied constraints among algorithms obstructed by the branching overlap gap property of Huang and Sellke [Huang and Sellke, 2025], notably including the Quantum Approximate Optimization Algorithm and all quantum circuits on a bounded-degree architecture of up to ε ⋅ log n depth [Chou et al., 2022].
Cite as

Antares Chen, Neng Huang, and Kunal Marwaha. Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 392, pp. 78:1-78:26, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.APPROX/RANDOM.2026.78,
  author =	{Chen, Antares and Huang, Neng and Marwaha, Kunal},
  title =	{{Local Algorithms and the Failure of Log-Depth Quantum Advantage on Sparse Random CSPs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026)},
  pages =	{78:1--78:26},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-449-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{392},
  editor =	{Singh, Mohit and Gur, Tom},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.78},
  URN =		{urn:nbn:de:0030-drops-277952},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2026.78},
  annote =	{Keywords: Random CSP, message-passing algorithm}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.19
On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems

Authors: Ian DeHaan, Neng Huang, and Euiwoong Lee

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We study minimum cost constraint satisfaction problems (MinCostCSP) through the algebraic lens. We show that for any constraint language Γ which has the dual discriminator operation as a polymorphism, there exists a |D|-approximation algorithm for MinCostCSP(Γ) where D is the domain. Complementing our algorithmic result, we show that any constraint language Γ where MinCostCSP(Γ) admits a constant-factor approximation must have a near-unanimity (NU) polymorphism unless P = NP, extending a similar result by Dalmau et al. on MinCSPs. These results imply a dichotomy of constant-factor approximability for constraint languages that contain all permutation relations (a natural generalization for Boolean CSPs that allow variable negation): either MinCostCSP(Γ) has an NU polymorphism and is |D|-approximable, or it does not have any NU polymorphism and is NP-hard to approximate within any constant factor. Finally, we present a constraint language which has a majority polymorphism, but is nonetheless NP-hard to approximate within any constant factor assuming the Unique Games Conjecture, showing that the condition of having an NU polymorphism is in general not sufficient unless UGC fails.
Cite as

Ian DeHaan, Neng Huang, and Euiwoong Lee. On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 19:1-19:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dehaan_et_al:LIPIcs.APPROX/RANDOM.2025.19,
  author =	{DeHaan, Ian and Huang, Neng and Lee, Euiwoong},
  title =	{{On the Constant-Factor Approximability of Minimum Cost Constraint Satisfaction Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{19:1--19:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  URN =		{urn:nbn:de:0030-drops-243851},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.19},
  annote =	{Keywords: Constraint satisfaction problems, approximation algorithms, polymorphisms}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2025.61
Hardness of Sampling for the Anti-Ferromagnetic Ising Model on Random Graphs

Authors: Neng Huang, Will Perkins, and Aaron Potechin

Published in: LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025)

Abstract
We prove a hardness of sampling result for the anti-ferromagnetic Ising model on random graphs of average degree d for large constant d, proving that when the normalized inverse temperature satisfies β > 1 (asymptotically corresponding to the condensation threshold), then w.h.p. over the random graph there is no stable sampling algorithm that can output a sample close in W₂ distance to the Gibbs measure. The results also apply to a fixed-magnetization version of the model, showing that there are no stable sampling algorithms for low but positive temperature max and min bisection distributions. These results show a gap in the tractability of search and sampling problems: while there are efficient algorithms to find near optimizers, stable sampling algorithms cannot access the Gibbs distribution concentrated on such solutions. Our techniques involve extensions of the interpolation technique relating behavior of the mean field Sherrington-Kirkpatrick model to behavior of Ising models on random graphs of average degree d for large d. While previous interpolation arguments compared the free energies of the two models, our argument compares the average energies and average overlaps in the two models.
Cite as

Neng Huang, Will Perkins, and Aaron Potechin. Hardness of Sampling for the Anti-Ferromagnetic Ising Model on Random Graphs. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 325, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.ITCS.2025.61,
  author =	{Huang, Neng and Perkins, Will and Potechin, Aaron},
  title =	{{Hardness of Sampling for the Anti-Ferromagnetic Ising Model on Random Graphs}},
  booktitle =	{16th Innovations in Theoretical Computer Science Conference (ITCS 2025)},
  pages =	{61:1--61:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-361-4},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{325},
  editor =	{Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.61},
  URN =		{urn:nbn:de:0030-drops-226899},
  doi =		{10.4230/LIPIcs.ITCS.2025.61},
  annote =	{Keywords: Random graph, spin glass, sampling algorithm}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.58
On the Approximability of Presidential Type Predicates

Authors: Neng Huang and Aaron Potechin

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
Given a predicate P: {-1, 1}^k → {-1, 1}, let CSP(P) be the set of constraint satisfaction problems whose constraints are of the form P. We say that P is approximable if given a nearly satisfiable instance of CSP(P), there exists a probabilistic polynomial time algorithm that does better than a random assignment. Otherwise, we say that P is approximation resistant. In this paper, we analyze presidential type predicates, which are balanced linear threshold functions where all of the variables except the first variable (the president) have the same weight. We show that almost all presidential type predicates P are approximable. More precisely, we prove the following result: for any δ₀ > 0, there exists a k₀ such that if k ≥ k₀, δ ∈ (δ₀,1 - 2/k], and {δ}k + k - 1 is an odd integer then the presidential type predicate P(x) = sign({δ}k{x₁} + ∑_{i = 2}^{k} {x_i}) is approximable. To prove this, we construct a rounding scheme that makes use of biases and pairwise biases. We also give evidence that using pairwise biases is necessary for such rounding schemes.
Cite as

Neng Huang and Aaron Potechin. On the Approximability of Presidential Type Predicates. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 58:1-58:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{huang_et_al:LIPIcs.APPROX/RANDOM.2020.58,
  author =	{Huang, Neng and Potechin, Aaron},
  title =	{{On the Approximability of Presidential Type Predicates}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{58:1--58:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.58},
  URN =		{urn:nbn:de:0030-drops-126612},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.58},
  annote =	{Keywords: constraint satisfaction problems, approximation algorithms, presidential type predicates}
}
Document
DOI: 10.4230/LIPIcs.ESA.2018.45
On the Decision Tree Complexity of String Matching

Authors: Xiaoyu He, Neng Huang, and Xiaoming Sun

Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)

Abstract
String matching is one of the most fundamental problems in computer science. A natural problem is to determine the number of characters that need to be queried (i.e. the decision tree complexity) in a string in order to decide whether this string contains a certain pattern. Rivest showed that for every pattern p, in the worst case any deterministic algorithm needs to query at least n-|p|+1 characters, where n is the length of the string and |p| is the length of the pattern. He further conjectured that this bound is tight. By using the adversary method, Tuza disproved this conjecture and showed that more than one half of binary patterns are evasive, i.e. any algorithm needs to query all the characters (see Section 1.1 for more details). In this paper, we give a query algorithm which settles the decision tree complexity of string matching except for a negligible fraction of patterns. Our algorithm shows that Tuza's criteria of evasive patterns are almost complete. Using the algebraic approach of Rivest and Vuillemin, we also give a new sufficient condition for the evasiveness of patterns, which is beyond Tuza's criteria. In addition, our result reveals an interesting connection to Skolem's Problem in mathematics.
Cite as

Xiaoyu He, Neng Huang, and Xiaoming Sun. On the Decision Tree Complexity of String Matching. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 45:1-45:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{he_et_al:LIPIcs.ESA.2018.45,
  author =	{He, Xiaoyu and Huang, Neng and Sun, Xiaoming},
  title =	{{On the Decision Tree Complexity of String Matching}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{45:1--45:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Azar, Yossi and Bast, Hannah and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.45},
  URN =		{urn:nbn:de:0030-drops-95082},
  doi =		{10.4230/LIPIcs.ESA.2018.45},
  annote =	{Keywords: String Matching, Decision Tree Complexity, Boolean Function, Algebraic Method}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact