TY - GEN
T1 - On the complexity of aggregating information for authentication and profiling
AU - Duncan, Christian A.
AU - Phoha, Vir V.
PY - 2012
Y1 - 2012
N2 - Motivated by applications in online privacy, user authentication and profiling, we discuss the complexity of various problems generalized from the classic 0-1 knapsack problem. In our scenarios, we assume the existence of a scoring function that evaluates the confidence in the personal online profile or authenticity of an individual based on a subset of acquired credentials and facts about an individual and show how the specific properties of that function affect the computational complexity of the problem, providing both NP-completeness proofs under certain conditions as well as pseudo-polynomial- time solutions under others.
AB - Motivated by applications in online privacy, user authentication and profiling, we discuss the complexity of various problems generalized from the classic 0-1 knapsack problem. In our scenarios, we assume the existence of a scoring function that evaluates the confidence in the personal online profile or authenticity of an individual based on a subset of acquired credentials and facts about an individual and show how the specific properties of that function affect the computational complexity of the problem, providing both NP-completeness proofs under certain conditions as well as pseudo-polynomial- time solutions under others.
KW - Computational complexity
KW - User profiling
UR - http://www.scopus.com/inward/record.url?scp=84903825871&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84903825871&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-28879-1_5
DO - 10.1007/978-3-642-28879-1_5
M3 - Conference contribution
AN - SCOPUS:84903825871
SN - 9783642288784
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 58
EP - 71
BT - Data Privacy Management and Autonomous Spontaneous Security - 6th International Workshop, DPM 2011, and 4th International Workshop, SETOP 2011, Revised Selected Papers
PB - Springer Verlag
T2 - 6th International Workshop on Data Privacy Management, DPM 2011 and 4th SETOP International Workshop on Autonomous and Spontaneous Security, SETOP 2011
Y2 - 15 September 2011 through 16 September 2011
ER -