VIP内容

Amanda J. Minnich是劳伦斯·利弗莫尔国家实验室（LLNL）的机器学习研究科学家和分子数据驱动的建模团队负责人。在LLNL，她是多机构ATOM联盟的成员，在那里她将机器学习技术应用于生物学数据以进行药物发现。 Minnich博士获得了加州大学伯克利分校的综合生物学学士学位（2009年），并获得了新墨西哥大学的计算机科学硕士学位（2014年）和杰出博士学位（2017年）。她的论文主题是“垃圾邮件，欺诈和僵尸程序：提高在线社交媒体数据的完整性”。在UNM期间，她被任命为NSF研究生研究员，PiBBs研究员，Grace Hopper学者以及该领域的杰出研究生。 CS部门在2017年发表了她的作品。她曾在包括WWW，ASONAM，KDD，ICDM，SC，GTC和ICWE在内的顶级会议的程序委员会上发表论文并任职，并因此获得了论文研究专利。 Minnich博士还热衷于倡导技术女性。她是UNM第一个特许的女性参与计算小组的联合创始人并担任总裁，她经常在科技活动中为女性做志愿者，她将在Grace Hopper Celebration 2019担任人工智能专题的联合主席。

Abdullah Mueen,新墨西哥大学计算机科学的助理教授。在此之前，他曾是Microsoft Corporation云和信息科学实验室的科学家。 他的主要兴趣是时间数据挖掘，重点是两种独特的信号类型：社交网络和电子传感器。 他一直积极参与数据挖掘会议，包括KDD，ICDM和SDM，以及包括DMKD和KAIS在内的期刊。 他在2012年KDD博士论文竞赛中获得亚军。他在SIGKDD 2012上获得了最佳论文奖。他的研究由NSF，DARPA和AFRL资助。 此前，他在加利福尼亚大学河滨分校获得博士学位，并在孟加拉国工程技术大学获得理学学士学位。

最新内容

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an s-bit advice on a randomly chosen function $f : [n] -> [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$, i.e., to find $x\in f^{-1}(y)$. Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman [IEEE transactions on Information Theory 80] presented an adaptive inverter that inverts with high probability a random $f$. Fiat and Naor [SICOMP 00] proved that for any $s$, $q$ with $s^3q = n$ (ignoring low-order terms), an $s$-advice, $q$-query variant of Hellmans algorithm inverts a constant fraction of the image points of any function. Yao [STOC 90] proved a lower bound of $sq \geq n$ for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question. Very little is known for the non-adaptive variant of the question. The only known upper bounds, i.e., inverters, are the trivial ones (with $s+q = n$), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC 19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that, for a strong enough choice of parameters, are notoriously hard to prove. We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters.

最新论文

We study time/memory tradeoffs of function inversion: an algorithm, i.e., an inverter, equipped with an s-bit advice on a randomly chosen function $f : [n] -> [n]$ and using $q$ oracle queries to $f$, tries to invert a randomly chosen output $y$ of $f$, i.e., to find $x\in f^{-1}(y)$. Much progress was done regarding adaptive function inversion - the inverter is allowed to make adaptive oracle queries. Hellman [IEEE transactions on Information Theory 80] presented an adaptive inverter that inverts with high probability a random $f$. Fiat and Naor [SICOMP 00] proved that for any $s$, $q$ with $s^3q = n$ (ignoring low-order terms), an $s$-advice, $q$-query variant of Hellmans algorithm inverts a constant fraction of the image points of any function. Yao [STOC 90] proved a lower bound of $sq \geq n$ for this problem. Closing the gap between the above lower and upper bounds is a long-standing open question. Very little is known for the non-adaptive variant of the question. The only known upper bounds, i.e., inverters, are the trivial ones (with $s+q = n$), and the only lower bound is the above bound of Yao. In a recent work, Corrigan-Gibbs and Kogan [TCC 19] partially justified the difficulty of finding lower bounds on non-adaptive inverters, showing that a lower bound on the time/memory tradeoff of non-adaptive inverters implies a lower bound on low-depth Boolean circuits. Bounds that, for a strong enough choice of parameters, are notoriously hard to prove. We make progress on the above intriguing question, both for the adaptive and the non-adaptive case, proving the following lower bounds on restricted families of inverters.

Top