Stop the war!Остановите войну!
for scientists:
default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDBibTeX records: Paul Valiant
@inproceedings{DBLP:conf/soda/SafranRV24,
author = {Itay Safran and
Daniel Reichman and
Paul Valiant},
editor = {David P. Woodruff},
title = {How Many Neurons Does it Take to Approximate the Maximum?},
booktitle = {Proceedings of the 2024 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2024, Alexandria, VA, USA, January 7-10, 2024},
pages = {3156--3183},
publisher = {{SIAM}},
year = {2024},
url = {https://doi.org/10.1137/1.9781611977912.113},
doi = {10.1137/1.9781611977912.113},
timestamp = {Thu, 04 Apr 2024 19:38:10 +0200},
biburl = {https://dblp.org/rec/conf/soda/SafranRV24.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2402-07248,
author = {Itay Safran and
Daniel Reichman and
Paul Valiant},
title = {Depth Separations in Neural Networks: Separating the Dimension from
the Accuracy},
journal = {CoRR},
volume = {abs/2402.07248},
year = {2024},
url = {https://doi.org/10.48550/arXiv.2402.07248},
doi = {10.48550/ARXIV.2402.07248},
eprinttype = {arXiv},
eprint = {2402.07248},
timestamp = {Fri, 16 Feb 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2402-07248.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/DangLSV23,
author = {Trung Dang and
Jasper C. H. Lee and
Maoyuan Raymond Song and
Paul Valiant},
editor = {Alice Oh and
Tristan Naumann and
Amir Globerson and
Kate Saenko and
Moritz Hardt and
Sergey Levine},
title = {Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond 1+{\(\alpha\)} Moments},
booktitle = {Advances in Neural Information Processing Systems 36: Annual Conference
on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans,
LA, USA, December 10 - 16, 2023},
year = {2023},
url = {http://papers.nips.cc/paper\_files/paper/2023/hash/0cddb777d3441326544e21b67f41bdc8-Abstract-Conference.html},
timestamp = {Fri, 01 Mar 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/DangLSV23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/GuptaL0V23,
author = {Shivam Gupta and
Jasper C. H. Lee and
Eric Price and
Paul Valiant},
editor = {Alice Oh and
Tristan Naumann and
Amir Globerson and
Kate Saenko and
Moritz Hardt and
Sergey Levine},
title = {Minimax-Optimal Location Estimation},
booktitle = {Advances in Neural Information Processing Systems 36: Annual Conference
on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans,
LA, USA, December 10 - 16, 2023},
year = {2023},
url = {http://papers.nips.cc/paper\_files/paper/2023/hash/02a589ef9a4f6f1e2dcc1cfb3b978a51-Abstract-Conference.html},
timestamp = {Mon, 22 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/nips/GuptaL0V23.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2307-09212,
author = {Itay Safran and
Daniel Reichman and
Paul Valiant},
title = {How Many Neurons Does it Take to Approximate the Maximum?},
journal = {CoRR},
volume = {abs/2307.09212},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2307.09212},
doi = {10.48550/ARXIV.2307.09212},
eprinttype = {arXiv},
eprint = {2307.09212},
timestamp = {Tue, 08 Aug 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2307-09212.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2311-12784,
author = {Trung Dang and
Jasper C. H. Lee and
Maoyuan Song and
Paul Valiant},
title = {Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian,
and Beyond 1+{\(\alpha\)} Moments},
journal = {CoRR},
volume = {abs/2311.12784},
year = {2023},
url = {https://doi.org/10.48550/arXiv.2311.12784},
doi = {10.48550/ARXIV.2311.12784},
eprinttype = {arXiv},
eprint = {2311.12784},
timestamp = {Wed, 29 Nov 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2311-12784.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/LeeV22,
author = {Jasper C. H. Lee and
Paul Valiant},
editor = {Mark Braverman},
title = {Optimal Sub-Gaussian Mean Estimation in Very High Dimensions},
booktitle = {13th Innovations in Theoretical Computer Science Conference, {ITCS}
2022, January 31 - February 3, 2022, Berkeley, CA, {USA}},
series = {LIPIcs},
volume = {215},
pages = {98:1--98:21},
publisher = {Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik},
year = {2022},
url = {https://doi.org/10.4230/LIPIcs.ITCS.2022.98},
doi = {10.4230/LIPICS.ITCS.2022.98},
timestamp = {Wed, 26 Jan 2022 14:33:51 +0100},
biburl = {https://dblp.org/rec/conf/innovations/LeeV22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/0002L0V22,
author = {Shivam Gupta and
Jasper C. H. Lee and
Eric Price and
Paul Valiant},
editor = {Sanmi Koyejo and
S. Mohamed and
A. Agarwal and
Danielle Belgrave and
K. Cho and
A. Oh},
title = {Finite-Sample Maximum Likelihood Estimation of Location},
booktitle = {Advances in Neural Information Processing Systems 35: Annual Conference
on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans,
LA, USA, November 28 - December 9, 2022},
year = {2022},
url = {http://papers.nips.cc/paper\_files/paper/2022/hash/c27cfb05a2e9eb579698419b25234ffb-Abstract-Conference.html},
timestamp = {Mon, 08 Jan 2024 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/0002L0V22.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2206-02348,
author = {Shivam Gupta and
Jasper C. H. Lee and
Eric Price and
Paul Valiant},
title = {Finite-Sample Maximum Likelihood Estimation of Location},
journal = {CoRR},
volume = {abs/2206.02348},
year = {2022},
url = {https://doi.org/10.48550/arXiv.2206.02348},
doi = {10.48550/ARXIV.2206.02348},
eprinttype = {arXiv},
eprint = {2206.02348},
timestamp = {Mon, 20 Jun 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-2206-02348.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LeeV21,
author = {Jasper C. H. Lee and
Paul Valiant},
title = {Optimal Sub-Gaussian Mean Estimation in {\textdollar}{\textbackslash}mathbb\{R\}{\textdollar}},
booktitle = {62nd {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2021, Denver, CO, USA, February 7-10, 2022},
pages = {672--683},
publisher = {{IEEE}},
year = {2021},
url = {https://doi.org/10.1109/FOCS52979.2021.00071},
doi = {10.1109/FOCS52979.2021.00071},
timestamp = {Wed, 09 Mar 2022 12:12:23 +0100},
biburl = {https://dblp.org/rec/conf/focs/LeeV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/LeeV21,
author = {Jasper C. H. Lee and
Paul Valiant},
editor = {D{\'{a}}niel Marx},
title = {Uncertainty about Uncertainty: Optimal Adaptive Algorithms for Estimating
Mixtures of Unknown Coins},
booktitle = {Proceedings of the 2021 {ACM-SIAM} Symposium on Discrete Algorithms,
{SODA} 2021, Virtual Conference, January 10 - 13, 2021},
pages = {414--433},
publisher = {{SIAM}},
year = {2021},
url = {https://doi.org/10.1137/1.9781611976465.25},
doi = {10.1137/1.9781611976465.25},
timestamp = {Thu, 15 Jul 2021 13:48:55 +0200},
biburl = {https://dblp.org/rec/conf/soda/LeeV21.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/colt/BlancGVV20,
author = {Guy Blanc and
Neha Gupta and
Gregory Valiant and
Paul Valiant},
editor = {Jacob D. Abernethy and
Shivani Agarwal},
title = {Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck
like process},
booktitle = {Conference on Learning Theory, {COLT} 2020, 9-12 July 2020, Virtual
Event [Graz, Austria]},
series = {Proceedings of Machine Learning Research},
volume = {125},
pages = {483--513},
publisher = {{PMLR}},
year = {2020},
url = {http://proceedings.mlr.press/v125/blanc20a.html},
timestamp = {Fri, 27 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/colt/BlancGVV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/ChenVV20,
author = {Justin Y. Chen and
Gregory Valiant and
Paul Valiant},
editor = {Hugo Larochelle and
Marc'Aurelio Ranzato and
Raia Hadsell and
Maria{-}Florina Balcan and
Hsuan{-}Tien Lin},
title = {Worst-Case Analysis for Randomly Collected Data},
booktitle = {Advances in Neural Information Processing Systems 33: Annual Conference
on Neural Information Processing Systems 2020, NeurIPS 2020, December
6-12, 2020, virtual},
year = {2020},
url = {https://proceedings.neurips.cc/paper/2020/hash/d34a281acc62c6bec66425f0ad6dd645-Abstract.html},
timestamp = {Tue, 19 Jan 2021 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/nips/ChenVV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@incollection{DBLP:books/cu/20/ValiantV20,
author = {Gregory Valiant and
Paul Valiant},
editor = {Tim Roughgarden},
title = {Instance Optimal Distribution Testing and Learning},
booktitle = {Beyond the Worst-Case Analysis of Algorithms},
pages = {506--526},
publisher = {Cambridge University Press},
year = {2020},
url = {https://doi.org/10.1017/9781108637435.029},
doi = {10.1017/9781108637435.029},
timestamp = {Mon, 04 Jan 2021 16:41:48 +0100},
biburl = {https://dblp.org/rec/books/cu/20/ValiantV20.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-2011-08384,
author = {Jasper C. H. Lee and
Paul Valiant},
title = {Optimal Sub-Gaussian Mean Estimation in {R}},
journal = {CoRR},
volume = {abs/2011.08384},
year = {2020},
url = {https://arxiv.org/abs/2011.08384},
eprinttype = {arXiv},
eprint = {2011.08384},
timestamp = {Thu, 19 Nov 2020 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-2011-08384.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-09080,
author = {Guy Blanc and
Neha Gupta and
Gregory Valiant and
Paul Valiant},
title = {Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck
like process},
journal = {CoRR},
volume = {abs/1904.09080},
year = {2019},
url = {http://arxiv.org/abs/1904.09080},
eprinttype = {arXiv},
eprint = {1904.09080},
timestamp = {Fri, 04 Sep 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-09080.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1904-09228,
author = {Jasper C. H. Lee and
Paul Valiant},
title = {Uncertainty about Uncertainty: Near-Optimal Adaptive Algorithms for
Estimating Binary Mixtures of Unknown Coins},
journal = {CoRR},
volume = {abs/1904.09228},
year = {2019},
url = {http://arxiv.org/abs/1904.09228},
eprinttype = {arXiv},
eprint = {1904.09228},
timestamp = {Fri, 26 Apr 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1904-09228.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1911-03605,
author = {Justin Y. Chen and
Gregory Valiant and
Paul Valiant},
title = {How bad is worst-case data if you know where it comes from?},
journal = {CoRR},
volume = {abs/1911.03605},
year = {2019},
url = {http://arxiv.org/abs/1911.03605},
eprinttype = {arXiv},
eprint = {1911.03605},
timestamp = {Sun, 01 Dec 2019 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/corr/abs-1911-03605.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/ValiantV17,
author = {Gregory Valiant and
Paul Valiant},
title = {Estimating the Unseen: Improved Estimators for Entropy and Other Properties},
journal = {J. {ACM}},
volume = {64},
number = {6},
pages = {37:1--37:41},
year = {2017},
url = {https://doi.org/10.1145/3125643},
doi = {10.1145/3125643},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/journals/jacm/ValiantV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/ValiantV17,
author = {Gregory Valiant and
Paul Valiant},
title = {An Automatic Inequality Prover and Instance Optimal Identity Testing},
journal = {{SIAM} J. Comput.},
volume = {46},
number = {1},
pages = {429--455},
year = {2017},
url = {https://doi.org/10.1137/151002526},
doi = {10.1137/151002526},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/ValiantV17.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/LeeV16,
author = {Jasper C. H. Lee and
Paul Valiant},
editor = {Irit Dinur},
title = {Optimizing Star-Convex Functions},
booktitle = {{IEEE} 57th Annual Symposium on Foundations of Computer Science, {FOCS}
2016, 9-11 October 2016, Hyatt Regency, New Brunswick, New Jersey,
{USA}},
pages = {603--614},
publisher = {{IEEE} Computer Society},
year = {2016},
url = {https://doi.org/10.1109/FOCS.2016.71},
doi = {10.1109/FOCS.2016.71},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/LeeV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ValiantV16,
author = {Gregory Valiant and
Paul Valiant},
editor = {Daniel Wichs and
Yishay Mansour},
title = {Instance optimal learning of discrete distributions},
booktitle = {Proceedings of the 48th Annual {ACM} {SIGACT} Symposium on Theory
of Computing, {STOC} 2016, Cambridge, MA, USA, June 18-21, 2016},
pages = {142--155},
publisher = {{ACM}},
year = {2016},
url = {https://doi.org/10.1145/2897518.2897641},
doi = {10.1145/2897518.2897641},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ValiantV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ValiantV16,
author = {Gregory Valiant and
Paul Valiant},
title = {Information Theoretically Secure Databases},
journal = {CoRR},
volume = {abs/1605.02646},
year = {2016},
url = {http://arxiv.org/abs/1605.02646},
eprinttype = {arXiv},
eprint = {1605.02646},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ValiantV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ValiantV16,
author = {Gregory Valiant and
Paul Valiant},
title = {Information Theoretically Secure Databases},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR16-078}},
year = {2016},
url = {https://eccc.weizmann.ac.il/report/2016/078},
eprinttype = {ECCC},
eprint = {TR16-078},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ValiantV16.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ValiantV15,
author = {Gregory Valiant and
Paul Valiant},
title = {Instance Optimal Learning},
journal = {CoRR},
volume = {abs/1504.05321},
year = {2015},
url = {http://arxiv.org/abs/1504.05321},
eprinttype = {arXiv},
eprint = {1504.05321},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ValiantV15.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/LeeV15a,
author = {Jasper C. H. Lee and
Paul Valiant},
title = {Beyond Convex Optimization: Star-Convex Functions},
journal = {CoRR},
volume = {abs/1511.04466},
year = {2015},
url = {http://arxiv.org/abs/1511.04466},
eprinttype = {arXiv},
eprint = {1511.04466},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/LeeV15a.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/toct/Valiant14,
author = {Paul Valiant},
title = {Evolvability of Real Functions},
journal = {{ACM} Trans. Comput. Theory},
volume = {6},
number = {3},
pages = {12:1--12:19},
year = {2014},
url = {https://doi.org/10.1145/2633598},
doi = {10.1145/2633598},
timestamp = {Mon, 08 Jun 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/toct/Valiant14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ValiantV14,
author = {Gregory Valiant and
Paul Valiant},
title = {An Automatic Inequality Prover and Instance Optimal Identity Testing},
booktitle = {55th {IEEE} Annual Symposium on Foundations of Computer Science, {FOCS}
2014, Philadelphia, PA, USA, October 18-21, 2014},
pages = {51--60},
publisher = {{IEEE} Computer Society},
year = {2014},
url = {https://doi.org/10.1109/FOCS.2014.14},
doi = {10.1109/FOCS.2014.14},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ValiantV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChanDVV14,
author = {Siu On Chan and
Ilias Diakonikolas and
Paul Valiant and
Gregory Valiant},
editor = {Chandra Chekuri},
title = {Optimal Algorithms for Testing Closeness of Discrete Distributions},
booktitle = {Proceedings of the Twenty-Fifth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2014, Portland, Oregon, USA, January 5-7, 2014},
pages = {1193--1203},
publisher = {{SIAM}},
year = {2014},
url = {https://doi.org/10.1137/1.9781611973402.88},
doi = {10.1137/1.9781611973402.88},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/ChanDVV14.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/nips/ValiantV13,
author = {Paul Valiant and
Gregory Valiant},
editor = {Christopher J. C. Burges and
L{\'{e}}on Bottou and
Zoubin Ghahramani and
Kilian Q. Weinberger},
title = {Estimating the Unseen: Improved Estimators for Entropy and other Properties},
booktitle = {Advances in Neural Information Processing Systems 26: 27th Annual
Conference on Neural Information Processing Systems 2013. Proceedings
of a meeting held December 5-8, 2013, Lake Tahoe, Nevada, United States},
pages = {2157--2165},
year = {2013},
url = {https://proceedings.neurips.cc/paper/2013/hash/53c04118df112c13a8c34b38343b9c10-Abstract.html},
timestamp = {Mon, 16 May 2022 15:41:51 +0200},
biburl = {https://dblp.org/rec/conf/nips/ValiantV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaskalakisDSVV13,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio and
Gregory Valiant and
Paul Valiant},
editor = {Sanjeev Khanna},
title = {Testing \emph{k}-Modal Distributions: Optimal Algorithms via Reductions},
booktitle = {Proceedings of the Twenty-Fourth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2013, New Orleans, Louisiana, USA, January 6-8,
2013},
pages = {1833--1852},
publisher = {{SIAM}},
year = {2013},
url = {https://doi.org/10.1137/1.9781611973105.131},
doi = {10.1137/1.9781611973105.131},
timestamp = {Tue, 02 Feb 2021 17:07:29 +0100},
biburl = {https://dblp.org/rec/conf/soda/DaskalakisDSVV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/ChanDVV13,
author = {Siu On Chan and
Ilias Diakonikolas and
Gregory Valiant and
Paul Valiant},
title = {Optimal Algorithms for Testing Closeness of Discrete Distributions},
journal = {CoRR},
volume = {abs/1308.3946},
year = {2013},
url = {http://arxiv.org/abs/1308.3946},
eprinttype = {arXiv},
eprint = {1308.3946},
timestamp = {Thu, 14 Sep 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/ChanDVV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ValiantV13,
author = {Gregory Valiant and
Paul Valiant},
title = {Instance-by-instance optimal identity testing},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR13-111}},
year = {2013},
url = {https://eccc.weizmann.ac.il/report/2013/111},
eprinttype = {ECCC},
eprint = {TR13-111},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ValiantV13.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/jacm/GottlobLVV12,
author = {Georg Gottlob and
Stephanie Tien Lee and
Gregory Valiant and
Paul Valiant},
title = {Size and Treewidth Bounds for Conjunctive Queries},
journal = {J. {ACM}},
volume = {59},
number = {3},
pages = {16:1--16:35},
year = {2012},
url = {https://doi.org/10.1145/2220357.2220363},
doi = {10.1145/2220357.2220363},
timestamp = {Sun, 02 Jun 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/jacm/GottlobLVV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/Valiant12,
author = {Paul Valiant},
editor = {Shafi Goldwasser},
title = {Distribution free evolvability of polynomial functions over all convex
loss functions},
booktitle = {Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA,
January 8-10, 2012},
pages = {142--148},
publisher = {{ACM}},
year = {2012},
url = {https://doi.org/10.1145/2090236.2090248},
doi = {10.1145/2090236.2090248},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/Valiant12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/McGregorV12,
author = {Andrew McGregor and
Paul Valiant},
editor = {Yuval Rabani},
title = {The shifting sands algorithm},
booktitle = {Proceedings of the Twenty-Third Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2012, Kyoto, Japan, January 17-19, 2012},
pages = {453--458},
publisher = {{SIAM}},
year = {2012},
url = {https://doi.org/10.1137/1.9781611973099.39},
doi = {10.1137/1.9781611973099.39},
timestamp = {Tue, 02 Feb 2021 17:07:31 +0100},
biburl = {https://dblp.org/rec/conf/soda/McGregorV12.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamcomp/Valiant11,
author = {Paul Valiant},
title = {Testing Symmetric Properties of Distributions},
journal = {{SIAM} J. Comput.},
volume = {40},
number = {6},
pages = {1927--1968},
year = {2011},
url = {https://doi.org/10.1137/080734066},
doi = {10.1137/080734066},
timestamp = {Sat, 27 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamcomp/Valiant11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/ValiantV11,
author = {Gregory Valiant and
Paul Valiant},
editor = {Rafail Ostrovsky},
title = {The Power of Linear Estimators},
booktitle = {{IEEE} 52nd Annual Symposium on Foundations of Computer Science, {FOCS}
2011, Palm Springs, CA, USA, October 22-25, 2011},
pages = {403--412},
publisher = {{IEEE} Computer Society},
year = {2011},
url = {https://doi.org/10.1109/FOCS.2011.81},
doi = {10.1109/FOCS.2011.81},
timestamp = {Thu, 23 Mar 2023 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/focs/ValiantV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/BhattacharyyaFRV11,
author = {Arnab Bhattacharyya and
Eldar Fischer and
Ronitt Rubinfeld and
Paul Valiant},
editor = {Bernard Chazelle},
title = {Testing monotonicity of distributions over general partial orders},
booktitle = {Innovations in Computer Science - {ICS} 2011, Tsinghua University,
Beijing, China, January 7-9, 2011. Proceedings},
pages = {239--252},
publisher = {Tsinghua University Press},
year = {2011},
url = {http://conference.iiis.tsinghua.edu.cn/ICS2011/content/papers/38.html},
timestamp = {Mon, 23 Mar 2020 08:26:00 +0100},
biburl = {https://dblp.org/rec/conf/innovations/BhattacharyyaFRV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/ValiantV11,
author = {Gregory Valiant and
Paul Valiant},
editor = {Lance Fortnow and
Salil P. Vadhan},
title = {Estimating the unseen: an n/log(n)-sample estimator for entropy and
support size, shown optimal via new CLTs},
booktitle = {Proceedings of the 43rd {ACM} Symposium on Theory of Computing, {STOC}
2011, San Jose, CA, USA, 6-8 June 2011},
pages = {685--694},
publisher = {{ACM}},
year = {2011},
url = {https://doi.org/10.1145/1993636.1993727},
doi = {10.1145/1993636.1993727},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/ValiantV11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-1112-5659,
author = {Constantinos Daskalakis and
Ilias Diakonikolas and
Rocco A. Servedio and
Gregory Valiant and
Paul Valiant},
title = {Testing {\textdollar}k{\textdollar}-Modal Distributions: Optimal Algorithms
via Reductions},
journal = {CoRR},
volume = {abs/1112.5659},
year = {2011},
url = {http://arxiv.org/abs/1112.5659},
eprinttype = {arXiv},
eprint = {1112.5659},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-1112-5659.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Valiant11,
author = {Paul Valiant},
title = {Distribution Free Evolvability of Polynomial Functions over all Convex
Loss Functions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR11-089}},
year = {2011},
url = {https://eccc.weizmann.ac.il/report/2011/089},
eprinttype = {ECCC},
eprint = {TR11-089},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Valiant11.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/innovations/ChenMV10,
author = {Jing Chen and
Silvio Micali and
Paul Valiant},
editor = {Andrew Chi{-}Chih Yao},
title = {Robustly Leveraging Collusion in Combinatorial Auctions},
booktitle = {Innovations in Computer Science - {ICS} 2010, Tsinghua University,
Beijing, China, January 5-7, 2010. Proceedings},
pages = {81--93},
publisher = {Tsinghua University Press},
year = {2010},
url = {http://conference.iiis.tsinghua.edu.cn/ICS2010/content/papers/7.html},
timestamp = {Wed, 04 Sep 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/innovations/ChenMV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/BhattacharyyaFRV10,
author = {Arnab Bhattacharyya and
Eldar Fischer and
Ronitt Rubinfeld and
Paul Valiant},
title = {Testing monotonicity of distributions over general partial orders},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-027}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/027},
eprinttype = {ECCC},
eprint = {TR10-027},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/BhattacharyyaFRV10.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ValiantV10b,
author = {Gregory Valiant and
Paul Valiant},
title = {A {CLT} and tight lower bounds for estimating entropy},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-179}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/179},
eprinttype = {ECCC},
eprint = {TR10-179},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ValiantV10b.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/ValiantV10c,
author = {Gregory Valiant and
Paul Valiant},
title = {Estimating the unseen: {A} sublinear-sample canonical estimator of
distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR10-180}},
year = {2010},
url = {https://eccc.weizmann.ac.il/report/2010/180},
eprinttype = {ECCC},
eprint = {TR10-180},
timestamp = {Tue, 27 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/ValiantV10c.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/DaskalakisSVV09,
author = {Constantinos Daskalakis and
Grant Schoenebeck and
Gregory Valiant and
Paul Valiant},
editor = {Claire Mathieu},
title = {On the complexity of Nash equilibria of action-graph games},
booktitle = {Proceedings of the Twentieth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2009, New York, NY, USA, January 4-6, 2009},
pages = {710--719},
publisher = {{SIAM}},
year = {2009},
url = {https://doi.org/10.1137/1.9781611973068.78},
doi = {10.1137/1.9781611973068.78},
timestamp = {Mon, 26 Jun 2023 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/soda/DaskalakisSVV09.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0909-2030,
author = {Gregory Valiant and
Paul Valiant},
title = {Size Bounds for Conjunctive Queries with General Functional Dependencies},
journal = {CoRR},
volume = {abs/0909.2030},
year = {2009},
url = {http://arxiv.org/abs/0909.2030},
eprinttype = {arXiv},
eprint = {0909.2030},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0909-2030.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@phdthesis{DBLP:phd/ndltd/Valiant08,
author = {Paul Valiant},
title = {Testing symmetric properties of distributions},
school = {Massachusetts Institute of Technology, Cambridge, MA, {USA}},
year = {2008},
url = {https://hdl.handle.net/1721.1/44717},
timestamp = {Wed, 04 May 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/phd/ndltd/Valiant08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/stoc/Valiant08,
author = {Paul Valiant},
editor = {Cynthia Dwork},
title = {Testing symmetric properties of distributions},
booktitle = {Proceedings of the 40th Annual {ACM} Symposium on Theory of Computing,
Victoria, British Columbia, Canada, May 17-20, 2008},
pages = {383--392},
publisher = {{ACM}},
year = {2008},
url = {https://doi.org/10.1145/1374376.1374432},
doi = {10.1145/1374376.1374432},
timestamp = {Tue, 06 Nov 2018 00:00:00 +0100},
biburl = {https://dblp.org/rec/conf/stoc/Valiant08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/tcc/Valiant08,
author = {Paul Valiant},
editor = {Ran Canetti},
title = {Incrementally Verifiable Computation or Proofs of Knowledge Imply
Time/Space Efficiency},
booktitle = {Theory of Cryptography, Fifth Theory of Cryptography Conference, {TCC}
2008, New York, USA, March 19-21, 2008},
series = {Lecture Notes in Computer Science},
volume = {4948},
pages = {1--18},
publisher = {Springer},
year = {2008},
url = {https://doi.org/10.1007/978-3-540-78524-8\_1},
doi = {10.1007/978-3-540-78524-8\_1},
timestamp = {Tue, 14 May 2019 10:00:47 +0200},
biburl = {https://dblp.org/rec/conf/tcc/Valiant08.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/abs-0802-1604,
author = {Constantinos Daskalakis and
Grant Schoenebeck and
Gregory Valiant and
Paul Valiant},
title = {On the Complexity of Nash Equilibria of Action-Graph Games},
journal = {CoRR},
volume = {abs/0802.1604},
year = {2008},
url = {http://arxiv.org/abs/0802.1604},
eprinttype = {arXiv},
eprint = {0802.1604},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/abs-0802-1604.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/soda/ChenTV07,
author = {Xi Chen and
Shang{-}Hua Teng and
Paul Valiant},
editor = {Nikhil Bansal and
Kirk Pruhs and
Clifford Stein},
title = {The approximation complexity of win-lose games},
booktitle = {Proceedings of the Eighteenth Annual {ACM-SIAM} Symposium on Discrete
Algorithms, {SODA} 2007, New Orleans, Louisiana, USA, January 7-9,
2007},
pages = {159--168},
publisher = {{SIAM}},
year = {2007},
url = {http://dl.acm.org/citation.cfm?id=1283383.1283401},
timestamp = {Tue, 15 Feb 2022 07:54:27 +0100},
biburl = {https://dblp.org/rec/conf/soda/ChenTV07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/eccc/Valiant07,
author = {Paul Valiant},
title = {Testing Symmetric Properties of Distributions},
journal = {Electron. Colloquium Comput. Complex.},
volume = {{TR07-135}},
year = {2007},
url = {https://eccc.weizmann.ac.il/eccc-reports/2007/TR07-135/index.html},
eprinttype = {ECCC},
eprint = {TR07-135},
timestamp = {Wed, 28 Sep 2022 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/eccc/Valiant07.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/infocom/VutukuruVKB06,
author = {Mythili Vutukuru and
Paul Valiant and
Swastik Kopparty and
Hari Balakrishnan},
title = {How to Construct a Correct and Scalable iBGP Configuration},
booktitle = {{INFOCOM} 2006. 25th {IEEE} International Conference on Computer Communications,
Joint Conference of the {IEEE} Computer and Communications Societies,
23-29 April 2006, Barcelona, Catalunya, Spain},
publisher = {{IEEE}},
year = {2006},
url = {https://doi.org/10.1109/INFOCOM.2006.122},
doi = {10.1109/INFOCOM.2006.122},
timestamp = {Wed, 16 Oct 2019 14:14:51 +0200},
biburl = {https://dblp.org/rec/conf/infocom/VutukuruVKB06.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/siamdm/GraafV05,
author = {Mart de Graaf and
Paul Valiant},
title = {Polynomial Representations of Symmetric Partial Boolean Functions},
journal = {{SIAM} J. Discret. Math.},
volume = {19},
number = {2},
pages = {481--488},
year = {2005},
url = {https://doi.org/10.1137/S0895480103433562},
doi = {10.1137/S0895480103433562},
timestamp = {Sat, 25 Apr 2020 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/siamdm/GraafV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/approx/Valiant05,
author = {Paul Valiant},
editor = {Chandra Chekuri and
Klaus Jansen and
Jos{\'{e}} D. P. Rolim and
Luca Trevisan},
title = {The Tensor Product of Two Codes Is Not Necessarily Robustly Testable},
booktitle = {Approximation, Randomization and Combinatorial Optimization, Algorithms
and Techniques, 8th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems, {APPROX} 2005 and 9th InternationalWorkshop
on Randomization and Computation, {RANDOM} 2005, Berkeley, CA, USA,
August 22-24, 2005, Proceedings},
series = {Lecture Notes in Computer Science},
volume = {3624},
pages = {472--481},
publisher = {Springer},
year = {2005},
url = {https://doi.org/10.1007/11538462\_40},
doi = {10.1007/11538462\_40},
timestamp = {Tue, 21 Sep 2021 09:36:24 +0200},
biburl = {https://dblp.org/rec/conf/approx/Valiant05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@inproceedings{DBLP:conf/focs/AbbottKV05,
author = {Timothy G. Abbott and
Daniel Kane and
Paul Valiant},
title = {On the Complexity of Two-PlayerWin-Lose Games},
booktitle = {46th Annual {IEEE} Symposium on Foundations of Computer Science {(FOCS}
2005), 23-25 October 2005, Pittsburgh, PA, USA, Proceedings},
pages = {113--122},
publisher = {{IEEE} Computer Society},
year = {2005},
url = {https://doi.org/10.1109/SFCS.2005.59},
doi = {10.1109/SFCS.2005.59},
timestamp = {Thu, 04 Apr 2024 01:00:00 +0200},
biburl = {https://dblp.org/rec/conf/focs/AbbottKV05.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/aam/Valiant04,
author = {Paul Valiant},
title = {Linear bounds on the North-East model and higher-dimensional analogs},
journal = {Adv. Appl. Math.},
volume = {33},
number = {1},
pages = {40--50},
year = {2004},
url = {https://doi.org/10.1016/j.aam.2003.07.001},
doi = {10.1016/J.AAM.2003.07.001},
timestamp = {Tue, 06 Aug 2019 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/aam/Valiant04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/ipl/Valiant04,
author = {Paul Valiant},
title = {The Log-Rank Conjecture and low degree polynomials},
journal = {Inf. Process. Lett.},
volume = {89},
number = {2},
pages = {99--103},
year = {2004},
url = {https://doi.org/10.1016/j.ipl.2003.09.020},
doi = {10.1016/J.IPL.2003.09.020},
timestamp = {Fri, 26 May 2017 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/ipl/Valiant04.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
@article{DBLP:journals/corr/quant-ph-0211179,
author = {Mart de Graaf and
Paul Valiant},
title = {Comparing {EQP} and MOD{\_}\{p{\^{}}k\}P using Polynomial Degree Lower
Bounds},
journal = {CoRR},
volume = {quant-ph/0211179},
year = {2002},
url = {http://arxiv.org/abs/quant-ph/0211179},
timestamp = {Mon, 13 Aug 2018 01:00:00 +0200},
biburl = {https://dblp.org/rec/journals/corr/quant-ph-0211179.bib},
bibsource = {dblp computer science bibliography, https://dblp.org}
}
a service of 
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-04-25 02:01 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
