基本信息
浏览量:38
职业迁徙
个人简介
My research: I have broad interests, with a focus on computational complexity---the study of the inherent limits of efficient computation.
A main goal of my current work is to better understand the limits of some powerful algorithmic paradigms for solving NP-hard problems. One such paradigm is kernelization. A kernelization reduction is an algorithm that tries to "shrink" problem instances, a preprocessing step which makes exhaustive search more feasible. A second algorithmic paradigm I've studied is intelligent random guessing, in which one tries to guess a solution to the given problem in a clever way where one's success probability is larger than the naïve approach (one may then run many trials to get a solution with high probability, or decide none exists). I've shown new limits to the kind of algorithms we can hope to develop by either of these approaches. This work has (I feel) involved an intriguing mix of computational, probabilistic, and information-theoretic ideas.
Another major strand in complexity theory is the study of non-standard proof systems, which incorporate features like interaction with provers, probabilistic verification, and the manipulation of quantum states. These brain-bending proofs are surprisingly powerful, and I've helped to further illuminate their power.
Yet another theme that fascinates me is joint computation---the common situation in which we have multiple computational tasks to perform simultaneously. When can we cleverly combine computations to make them more efficient and reliable? Much of my work aims at better understanding the possibility and also the limits of such "computational synergies."
Outside of complexity theory, I've worked on problems in prediction and polynomial approximation. I also have a personal interest in using algorithmic ideas to better understand the power of human memory.
A main goal of my current work is to better understand the limits of some powerful algorithmic paradigms for solving NP-hard problems. One such paradigm is kernelization. A kernelization reduction is an algorithm that tries to "shrink" problem instances, a preprocessing step which makes exhaustive search more feasible. A second algorithmic paradigm I've studied is intelligent random guessing, in which one tries to guess a solution to the given problem in a clever way where one's success probability is larger than the naïve approach (one may then run many trials to get a solution with high probability, or decide none exists). I've shown new limits to the kind of algorithms we can hope to develop by either of these approaches. This work has (I feel) involved an intriguing mix of computational, probabilistic, and information-theoretic ideas.
Another major strand in complexity theory is the study of non-standard proof systems, which incorporate features like interaction with provers, probabilistic verification, and the manipulation of quantum states. These brain-bending proofs are surprisingly powerful, and I've helped to further illuminate their power.
Yet another theme that fascinates me is joint computation---the common situation in which we have multiple computational tasks to perform simultaneously. When can we cleverly combine computations to make them more efficient and reliable? Much of my work aims at better understanding the possibility and also the limits of such "computational synergies."
Outside of complexity theory, I've worked on problems in prediction and polynomial approximation. I also have a personal interest in using algorithmic ideas to better understand the power of human memory.
研究兴趣
论文共 29 篇作者统计合作学者相似作者
按年份排序按引用量排序主题筛选期刊级别筛选合作者筛选合作机构筛选
时间
引用量
主题
期刊级别
合作者
合作机构
International Computing and Combinatorics Conference (2024): 392-403
2021 IEEE International Conference on Quantum Computing and Engineering (QCE) (2021): 276-290
IACR Cryptol. ePrint Arch. (2020): 1195-485
FOCS '12 Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Scienceno. 5 (2015): 1443.0-1479.0
SIAM JOURNAL ON COMPUTINGno. 3 (2014): 1131-1183
PODCpp.367-376, (2014)
加载更多
作者统计
合作学者
合作机构
D-Core
- 合作者
- 学生
- 导师
数据免责声明
页面数据均来自互联网公开来源、合作出版商和通过AI技术自动分析结果,我们不对页面数据的有效性、准确性、正确性、可靠性、完整性和及时性做出任何承诺和保证。若有疑问,可以通过电子邮件方式联系我们:report@aminer.cn