학술논문
On the hardness of approximating the min-hack problem.
Document Type
Journal
Author
Chinchani, Ramkumar (1-SUNYB-CSE) AMS Author Profile; Ha, Duc (1-SUNYB-CSE) AMS Author Profile; Iyer, Anusha (1-SUNYB-CSE) AMS Author Profile; Ngo, Hung Q. (1-SUNYB-CSE) AMS Author Profile; Upadhyaya, Shambhu (1-SUNYB-CSE) AMS Author Profile
Source
Subject
90 Operations research, mathematical programming -- 90B Operations research and management science
90B10Network models, deterministic
90Operations research, mathematical programming -- 90C Mathematical programming
90C35Programming involving graphs or networks
90C60Abstract computational complexity for mathematical programming problems
94Information and communication, circuits -- 94A Communication, information
94A62Authentication and secret sharing
90B10
90
90C35
90C60
94
94A62
Language
English
Abstract
Summary: ``We show several hardness results for the minimum hacking problem, which can be described roughly as the problem of finding the best way to compromise a target node given a few initial compromised nodes in a network. We give several reductions to show that minimum hacking is not approximable to within $2^{(\log n)^{1-\delta}}$ where $\delta=1-{1\over\log\log^cn}$, for any $c<1/2$. We also analyze some heuristics on this problem.''