Zobrazeno 1 - 10
of 22
pro vyhledávání: '"Varun Kanade"'
Publikováno v:
Quantum Information and Computation. 19:1261-1278
We show that DNF formulae can be quantum PAC-learned in polynomial time under product distributions using a quantum example oracle. The best classical algorithm (without access to membership queries) runs in superpolynomial time. Our result extends t
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a49fd46c32f18524934e05d96ca24819
https://doi.org/10.26421/qic19.15-16-1
https://doi.org/10.26421/qic19.15-16-1
Publikováno v:
Scopus-Elsevier
Coalescing random walks is a fundamental distributed process, where a set of particles perform independent discrete-time random walks on an undirected graph. Whenever two or more particles meet at a given node, they merge and continue as a single ran
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ccbf9af8f001cfca42363d92196c7086
https://ora.ox.ac.uk/objects/uuid:0c47a2d5-7154-4bf8-8f88-a8a454b55b91
https://ora.ox.ac.uk/objects/uuid:0c47a2d5-7154-4bf8-8f88-a8a454b55b91
Publikováno v:
Scopus-Elsevier
Discovering statistical structure from links is a fundamental problem in the analysis of social networks. Choosing a misspecified model, or equivalently, an incorrect inference algorithm will result in an invalid analysis or even falsely uncover patt
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::42cae2f6e805b185ff63b5ee4c55e56e
https://ora.ox.ac.uk/objects/uuid:73693a08-95d2-4372-b7d3-8227577d2929
https://ora.ox.ac.uk/objects/uuid:73693a08-95d2-4372-b7d3-8227577d2929
Publikováno v:
Scopus-Elsevier
Hiererachical clustering, that is computing a recursive partitioning of a dataset to obtain clusters at increasingly finer granularity is a fundamental problem in data analysis. Although hierarchical clustering has mostly been studied through procedu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=dedup_wf_001::bdca1af11e6cb4fb46917ed006196144
https://ora.ox.ac.uk/objects/uuid:8447be4b-ee2f-421f-85e0-a81764d9681b
https://ora.ox.ac.uk/objects/uuid:8447be4b-ee2f-421f-85e0-a81764d9681b
Publikováno v:
PODC
We consider the problem of estimating the graph size, where one is given only local access to the graph. We formally define a query model in which one starts with a seed node and is allowed to make queries about neighbours of nodes that have already
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::403680864b5135df37e47f2503abc9d6
https://doi.org/10.1145/3087801.3087855
https://doi.org/10.1145/3087801.3087855
Publikováno v:
Scopus-Elsevier
It is well known that in many applications erroneous predictions of one type or another must be avoided. In some applications, like spam detection, false positive errors are serious problems. In other applications, like medical diagnosis, abstaining
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6f3ea439cd8ab9c564ca7fd5bac39838
https://doi.org/10.1016/j.jcss.2011.12.026
https://doi.org/10.1016/j.jcss.2011.12.026
Publikováno v:
Lecture Notes in Computer Science ISBN: 9783319244853
ALT
ALT
We study the problem of learning in the presence of a drifting target concept. Specifically, we provide bounds on the error rate at a given time, given a learner with access to a history of independent samples labeled according to a target concept th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::16c1a1a8111a7a5eaf758ce47eda945f
https://doi.org/10.1007/978-3-319-24486-0_10
https://doi.org/10.1007/978-3-319-24486-0_10
Autor:
Elaine Angelino, Varun Kanade
Publikováno v:
ITCS
In a seminal paper, Valiant (2006) introduced a computational model for evolution to address the question of complexity that can arise through Darwinian mechanisms. Valiant views evolution as a restricted form of computational learning, where the goa
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d7332f03b73a2d88e2383de929ae4bcd
https://doi.org/10.1145/2554797.2554824
https://doi.org/10.1145/2554797.2554824
Autor:
Varun Kanade, Mossel, E.
Publikováno v:
Scopus-Elsevier
The theory of learning under the uniform distribution is rich and deep, with connections to cryptography, computational complexity, and the analysis of boolean functions to name a few areas. This theory however is very limited due to the fact that th
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::414986a492460a28555f41ab71530819
http://arxiv.org/abs/1307.3617
http://arxiv.org/abs/1307.3617