Остановите войну!
for scientists:
default search action
Eric Blais
- > Home > Persons > Eric Blais
Publications
- 2024
- [c35]Hadley Black, Eric Blais, Nathaniel Harms:
Testing and Learning Convex Sets in the Ternary Hypercube. ITCS 2024: 15:1-15:21 - 2023
- [j17]Shalev Ben-David, Eric Blais:
A New Minimax Theorem for Randomized Algorithms. J. ACM 70(6): 38:1-38:58 (2023) - [i27]Hadley Black, Eric Blais, Nathaniel Harms:
Testing Convexity of Discrete Sets in High Dimensions. CoRR abs/2305.03194 (2023) - 2022
- [c33]Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre:
Randomised Composition and Small-Bias Minimax. FOCS 2022: 624-635 - [i25]Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre:
Randomised Composition and Small-Bias Minimax. CoRR abs/2208.12896 (2022) - [i24]Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre:
Randomised Composition and Small-Bias Minimax. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j16]Aleksandrs Belovs, Eric Blais:
A Polynomial Lower Bound for Testing Monotonicity. SIAM J. Comput. 50(3) (2021) - [c31]Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms:
VC dimension and distribution-free sample-based testing. STOC 2021: 504-517 - 2020
- [c30]Eric Blais, Abhinav Bommireddi:
On Testing and Robust Characterizations of Convexity. APPROX-RANDOM 2020: 18:1-18:15 - [c29]Shalev Ben-David, Eric Blais:
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract. FOCS 2020: 240-246 - [c28]Shalev Ben-David, Eric Blais:
A New Minimax Theorem for Randomized Algorithms (Extended Abstract). FOCS 2020: 403-411 - [c27]Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi:
Testing convexity of functions over finite domains. SODA 2020: 2030-2045 - [i23]Shalev Ben-David, Eric Blais:
A New Minimax Theorem for Randomized Algorithms. CoRR abs/2002.10802 (2020) - [i22]Shalev Ben-David, Eric Blais:
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions. CoRR abs/2002.10809 (2020) - [i21]Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms:
VC Dimension and Distribution-Free Sample-Based Testing. CoRR abs/2012.03923 (2020) - 2019
- [j15]Eric Blais, Yuichi Yoshida:
A characterization of constant-sample testable properties. Random Struct. Algorithms 55(1): 73-88 (2019) - [j14]Eric Blais, Clément L. Canonne, Tom Gur:
Distribution Testing Lower Bounds via Reductions from Communication Complexity. ACM Trans. Comput. Theory 11(2): 6:1-6:37 (2019) - [j13]Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. ACM Trans. Comput. Theory 11(4): 24:1-24:33 (2019) - [c26]Eric Blais, Joshua Brody:
Optimal Separation and Strong Direct Sum for Randomized Query Complexity. CCC 2019: 29:1-29:17 - [i20]Eric Blais, Joshua Brody:
Optimal Separation and Strong Direct Sum for Randomized Query Complexity. CoRR abs/1908.01020 (2019) - [i19]Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi:
Testing convexity of functions over finite domains. CoRR abs/1908.02525 (2019) - 2018
- [c25]Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. SODA 2018: 2113-2132 - [e1]Eric Blais, Klaus Jansen, José D. P. Rolim, David Steurer:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, August 20-22, 2018 - Princeton, NJ, USA. LIPIcs 116, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2018, ISBN 978-3-95977-085-9 [contents] - 2017
- [j12]Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld:
I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making. Proc. VLDB Endow. 10(11): 1262-1273 (2017) - [c23]Eric Blais, Clément L. Canonne, Tom Gur:
Distribution Testing Lower Bounds via Reductions from Communication Complexity. CCC 2017: 28:1-28:40 - [c22]Eric Blais, Abhinav Bommireddi:
Testing Submodularity and Other Properties of Valuation Functions. ITCS 2017: 33:1-33:17 - 2016
- [c21]Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld:
Learning and Testing Junta Distributions. COLT 2016: 19-46 - [c19]Aleksandrs Belovs, Eric Blais:
A polynomial lower bound for testing monotonicity. STOC 2016: 1021-1032 - [p2]Ronitt Rubinfeld, Eric Blais:
Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms. Handbook of Big Data 2016: 155-167 - [i17]Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. CoRR abs/1607.03938 (2016) - [i16]Eric Blais, Abhinav Bommireddi:
Testing submodularity and other properties of valuation functions. CoRR abs/1611.07879 (2016) - [i15]Eric Blais, Yuichi Yoshida:
A Characterization of Constant-Sample Testable Properties. CoRR abs/1612.06016 (2016) - [i14]Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron:
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. Electron. Colloquium Comput. Complex. TR16 (2016) - [i13]Eric Blais, Clément Louis Canonne, Tom Gur:
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.). Electron. Colloquium Comput. Complex. TR16 (2016) - [i12]Eric Blais, Yuichi Yoshida:
A Characterization of Constant-Sample Testable Properties. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j11]Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld:
Rapid Sampling for Visualizations with Ordering Guarantees. Proc. VLDB Endow. 8(5): 521-532 (2015) - [j10]Eric Blais, Amit Weinstein, Yuichi Yoshida:
Partially Symmetric Functions Are Efficiently Isomorphism Testable. SIAM J. Comput. 44(2): 411-432 (2015) - [j9]Eric Blais, Li-Yang Tan:
Approximating Boolean Functions with Depth-2 Circuits. SIAM J. Comput. 44(6): 1583-1600 (2015) - [j8]Aleksandrs Belovs, Eric Blais:
Quantum Algorithm for Monotonicity Testing on the Hypercube. Theory Comput. 11: 403-412 (2015) - [c18]Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning Circuits with few Negations. APPROX-RANDOM 2015: 512-527 - [i11]Aleksandrs Belovs, Eric Blais:
Quantum Algorithm for Monotonicity Testing on the Hypercube. CoRR abs/1503.02868 (2015) - [i10]Eric Blais, Li-Yang Tan, Andrew Wan:
An inequality for the Fourier spectrum of parity decision trees. CoRR abs/1506.01055 (2015) - [i9]Aleksandrs Belovs, Eric Blais:
A Polynomial Lower Bound for Testing Monotonicity. CoRR abs/1511.05053 (2015) - 2014
- [j7]Eric Blais, Amit Weinstein, Yuichi Yoshida:
Semi-Strong Colouring of Intersecting Hypergraphs. Comb. Probab. Comput. 23(1): 1-7 (2014) - [c16]Eric Blais, Joshua Brody, Badih Ghazi:
The Information Complexity of Hamming Distance. APPROX-RANDOM 2014: 465-489 - [c15]Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lower Bounds for Testing Properties of Functions over Hypergrid Domains. CCC 2014: 309-320 - [c14]Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan:
On DNF Approximators for Monotone Boolean Functions. ICALP (1) 2014: 235-246 - [i8]Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. CoRR abs/1410.8420 (2014) - [i7]Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Sam Madden, Ronitt Rubinfeld:
Rapid Sampling for Visualizations with Ordering Guarantees. CoRR abs/1412.3040 (2014) - [i6]Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j6]Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah:
Nearly Tight Bounds for Testing Function Isomorphism. SIAM J. Comput. 42(2): 459-493 (2013) - [j5]Eric Blais, Li-Yang Tan:
Hypercontractivity Via the Entropy Method. Theory Comput. 9: 889-896 (2013) - [c13]Eric Blais, Li-Yang Tan:
Approximating Boolean Functions with Depth-2 Circuits. CCC 2013: 74-85 - [i5]Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev:
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. TR13 (2013) - [i4]Eric Blais, Li-Yang Tan:
Approximating Boolean functions with depth-2 circuits. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j4]Eric Blais, Joshua Brody, Kevin Matulef:
Property Testing Lower Bounds via Communication Complexity. Comput. Complex. 21(2): 311-358 (2012) - [c12]Eric Blais, Daniel M. Kane:
Tight Bounds for Testing k-Linearity. APPROX-RANDOM 2012: 435-446 - [c11]Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang:
Active Property Testing. FOCS 2012: 21-30 - [c10]Eric Blais, Amit Weinstein, Yuichi Yoshida:
Partially Symmetric Functions Are Efficiently Isomorphism-Testable. FOCS 2012: 551-560 - 2011
- [c9]Eric Blais, Joshua Brody, Kevin Matulef:
Property Testing Lower Bounds via Communication Complexity. CCC 2011: 210-220 - [i3]Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang:
Active Testing. CoRR abs/1111.0897 (2011) - [i2]Eric Blais, Amit Weinstein, Yuichi Yoshida:
Partially Symmetric Functions are Efficiently Isomorphism-Testable. CoRR abs/1112.5741 (2011) - [i1]Eric Blais, Joshua Brody, Kevin Matulef:
Property Testing Lower Bounds via Communication Complexity. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j3]Eric Blais, Ryan O'Donnell, Karl Wimmer:
Polynomial regression under arbitrary product distributions. Mach. Learn. 80(2-3): 273-294 (2010) - [c8]James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo:
k + Decision Trees - (Extended Abstract). ALGOSENSORS 2010: 74-88 - [c7]Noga Alon, Eric Blais:
Testing Boolean Function Isomorphism. APPROX-RANDOM 2010: 394-405 - [c6]Eric Blais, Ryan O'Donnell:
Lower Bounds for Testing Function Isomorphism. CCC 2010: 235-246 - 2008
- [c3]Eric Blais, Ryan O'Donnell, Karl Wimmer:
Polynomial Regression under Arbitrary Product Distributions. COLT 2008: 193-204
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.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-21 17:09 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint