2 citations · 2 across the 2 of their papers we have counts for
6 papers
Feature Homomorphism -- A Cryptographic Scheme For Data Verification Under Ciphertext-Only Conditions
Huang Neng
Privacy computing involves the extensive exchange and processing of encrypted data. For the parties involved in these interactions, how to determine the consistency of exchanged da…
Separating MAX 2-AND, MAX DI-CUT and MAX CUT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
Assuming the Unique Games Conjecture (UGC), the best approximation ratio that can be obtained in polynomial time for the MAX CUT problem is , obtained…
On the Mysteries of MAX NAE-SAT
Joshua Brakensiek, Neng Huang, Aaron Potechin +1
MAX NAE-SAT is a natural optimization problem, closely related to its better-known relative MAX SAT. The approximability status of MAX NAE-SAT is almost completely understood if al…
On the Approximability of Presidential Type Predicates
Neng Huang, Aaron Potechin
Given a predicate , let be the set of constraint satisfaction problems whose constraints are of the form . We say that is approximable…
The idemetric property: when most distances are (almost) the same
George Barmpalias, Neng Huang, Andrew Lewis-Pye +4
We introduce the \emph{idemetric} property, which formalises the idea that most nodes in a graph have similar distances between them, and which turns out to be quite standard among…
On the Decision Tree Complexity of String Matching
Xiaoyu He, Neng Huang, Xiaoming Sun
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 t…