Abstract:
The
monotone boolean function that satisfies certain conditions
can be used in hardness amplification in NP problems. Proper
modifications to such function will construct a hardness
amplifier in NP. My talk is about constructing such monotone
boolean functions with better amplification parameters,
meanwhile, I want to propose more efficient construct of
such monotone boolean functions.
Biography:
Ms.
Jing He is a senior student of Tsinghua-Microsoft Special
Pilot CS Class, Tsinghua University and also an incoming
P.H.D student in Institute for Theoretical Computer Science
in Tsinghua University. My research interests are mainly
in theoretical computer science, especially hardness amplification
in NP problems. My final year project in Tsinghua University
is about the sensitivity of monotone Boolean functions.