Eric Blais

Publication Activity (10 Years)

Years Active: 2006-2024
Publications (10 Years): 50

Top Topics

Randomized Algorithm

Boolean Functions

Top Venues

Electron. Colloquium Comput. Complex.

Publications

Hadley Black, Eric Blais, Nathaniel Harms
Testing and Learning Convex Sets in the Ternary Hypercube. ITCS (2024)
Eric Blais, Cameron Seth
New Graph and Hypergraph Container Lemmas with Applications in Property Testing. CoRR (2024)
Eric Blais, Cameron Seth
New Graph and Hypergraph Container Lemmas with Applications in Property Testing. STOC (2024)
Eric Blais, Cameron Seth
Testing Graph Properties with the Container Method. CoRR (2023)
Eric Blais, Cameron Seth
Testing Graph Properties with the Container Method. FOCS (2023)
Shalev Ben-David, Eric Blais
A New Minimax Theorem for Randomized Algorithms. J. ACM 70 (6) (2023)
Hadley Black, Eric Blais, Nathaniel Harms
Testing Convexity of Discrete Sets in High Dimensions. CoRR (2023)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. Electron. Colloquium Comput. Complex. (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. FOCS (2022)
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
Randomised Composition and Small-Bias Minimax. CoRR (2022)
Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
VC dimension and distribution-free sample-based testing. STOC (2021)
Aleksandrs Belovs, Eric Blais
A Polynomial Lower Bound for Testing Monotonicity. SIAM J. Comput. 50 (3) (2021)
Kaleb Alway, Eric Blais, Semih Salihoglu
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing. ICDT (2021)
Shalev Ben-David, Eric Blais
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions. CoRR (2020)
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
Testing convexity of functions over finite domains. SODA (2020)
Shalev Ben-David, Eric Blais
A New Minimax Theorem for Randomized Algorithms (Extended Abstract). FOCS (2020)
Shalev Ben-David, Eric Blais
A New Minimax Theorem for Randomized Algorithms. CoRR (2020)
Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
VC Dimension and Distribution-Free Sample-Based Testing. CoRR (2020)
Eric Blais, Abhinav Bommireddi
On Testing and Robust Characterizations of Convexity. APPROX-RANDOM (2020)
Shalev Ben-David, Eric Blais
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract. FOCS (2020)
Eric Blais, Joshua Brody
Optimal Separation and Strong Direct Sum for Randomized Query Complexity. Computational Complexity Conference (2019)
Eric Blais, Clément L. Canonne, Tom Gur
Distribution Testing Lower Bounds via Reductions from Communication Complexity. ACM Trans. Comput. Theory 11 (2) (2019)
Eric Blais, Joshua Brody
Optimal Separation and Strong Direct Sum for Randomized Query Complexity. CoRR (2019)
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) (2019)
Eric Blais, Yuichi Yoshida
A characterization of constant-sample testable properties. Random Struct. Algorithms 55 (1) (2019)
Kaleb Alway, Eric Blais, Semih Salihoglu
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing. CoRR (2019)
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
Testing convexity of functions over finite domains. CoRR (2019)
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)
Eric Blais, Abhinav Bommireddi
Testing Submodularity and Other Properties of Valuation Functions. ITCS (2017)
Eric Blais, Clément L. Canonne, Tom Gur
Distribution Testing Lower Bounds via Reductions from Communication Complexity. Computational Complexity Conference (2017)
Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Peter van Beek
A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization. Canadian Conference on AI (2017)
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) (2017)
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 (2016)
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Huiqun Yu
A mathematical model of performance-relevant feature interactions. SPLC (2016)
Eric Blais, Yuichi Yoshida
A Characterization of Constant-Sample Testable Properties. CoRR (2016)
Aleksandrs Belovs, Eric Blais
A polynomial lower bound for testing monotonicity. STOC (2016)
Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld
Learning and Testing Junta Distributions. COLT (2016)
Eric Blais, Abhinav Bommireddi
Testing submodularity and other properties of valuation functions. CoRR (2016)
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. 23 (2016)
Eric Blais, Yuichi Yoshida
A Characterization of Constant-Sample Testable Properties. Electron. Colloquium Comput. Complex. 23 (2016)
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. 23 (2016)
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) (2015)
Aleksandrs Belovs, Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube. CoRR (2015)
Eric Blais, Li-Yang Tan, Andrew Wan
An inequality for the Fourier spectrum of parity decision trees. CoRR (2015)
Eric Blais, Li-Yang Tan
Approximating Boolean Functions with Depth-2 Circuits. SIAM J. Comput. 44 (6) (2015)
Eric Blais, Amit Weinstein, Yuichi Yoshida
Partially Symmetric Functions Are Efficiently Isomorphism Testable. SIAM J. Comput. 44 (2) (2015)
Aleksandrs Belovs, Eric Blais
A Polynomial Lower Bound for Testing Monotonicity. CoRR (2015)
Aleksandrs Belovs, Eric Blais
Quantum Algorithm for Monotonicity Testing on the Hypercube. Theory Comput. 11 (2015)
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki
Performance Prediction of Configurable Software Systems by Fourier Learning (T). ASE (2015)
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Learning Circuits with few Negations. APPROX-RANDOM (2015)
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Learning circuits with few negations. CoRR (2014)
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
Learning circuits with few negations. Electron. Colloquium Comput. Complex. 21 (2014)
Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan
On DNF Approximators for Monotone Boolean Functions. ICALP (1) (2014)
Eric Blais, Amit Weinstein, Yuichi Yoshida
Semi-Strong Colouring of Intersecting Hypergraphs. Comb. Probab. Comput. 23 (1) (2014)
Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Sam Madden, Ronitt Rubinfeld
Rapid Sampling for Visualizations with Ordering Guarantees. CoRR (2014)
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Lower Bounds for Testing Properties of Functions over Hypergrid Domains. Computational Complexity Conference (2014)
Eric Blais, Joshua Brody, Badih Ghazi
The Information Complexity of Hamming Distance. APPROX-RANDOM (2014)
Eric Blais, Li-Yang Tan
Hypercontractivity Via the Entropy Method. Theory Comput. 9 (2013)
Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah
Nearly Tight Bounds for Testing Function Isomorphism. SIAM J. Comput. 42 (2) (2013)
Eric Blais, Li-Yang Tan
Approximating Boolean functions with depth-2 circuits. Electron. Colloquium Comput. Complex. 20 (2013)
Eric Blais, Li-Yang Tan
Approximating Boolean Functions with Depth-2 Circuits. Computational Complexity Conference (2013)
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
Lower Bounds for Testing Properties of Functions on Hypergrid Domains. Electron. Colloquium Comput. Complex. 20 (2013)
Eric Blais, Joshua Brody, Kevin Matulef
Property Testing Lower Bounds via Communication Complexity. Comput. Complex. 21 (2) (2012)
Eric Blais, Daniel M. Kane
Tight Bounds for Testing k-Linearity. APPROX-RANDOM (2012)
Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang
Active Property Testing. FOCS (2012)
Eric Blais, Amit Weinstein, Yuichi Yoshida
Partially Symmetric Functions Are Efficiently Isomorphism-Testable. FOCS (2012)
Eric Blais, Amit Weinstein, Yuichi Yoshida
Partially Symmetric Functions are Efficiently Isomorphism-Testable CoRR (2011)
Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang
Active Testing CoRR (2011)
Eric Blais, Joshua Brody, Kevin Matulef
Property Testing Lower Bounds via Communication Complexity. Computational Complexity Conference (2011)
Eric Blais, Joshua Brody, Kevin Matulef
Property Testing Lower Bounds via Communication Complexity. Electron. Colloquium Comput. Complex. 18 (2011)
Eric Blais, Ryan O'Donnell
Lower Bounds for Testing Function Isomorphism. Computational Complexity Conference (2010)
Noga Alon, Eric Blais
Testing Boolean Function Isomorphism. APPROX-RANDOM (2010)
James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo
Decision Trees - (Extended Abstract). ALGOSENSORS (2010)
Eric Blais, Ryan O'Donnell, Karl Wimmer
Polynomial regression under arbitrary product distributions. Mach. Learn. 80 (2-3) (2010)
Eric Blais
Testing juntas nearly optimally. STOC (2009)
Eric Blais, Ryan O'Donnell, Karl Wimmer
Polynomial Regression under Arbitrary Product Distributions. COLT (2008)
Eric Blais
Improved Bounds for Testing Juntas. APPROX-RANDOM (2008)
Guillaume Blin, Eric Blais, Danny Hermelin, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk
Gene Maps Linearization Using Genomic Rearrangement Distances. J. Comput. Biol. 14 (4) (2007)
Guillaume Blin, Eric Blais, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk
Inferring Gene Orders from Gene Maps Using the Breakpoint Distance. Comparative Genomics (2006)
Eric Blais, Mathieu Blanchette
Common Substrings in Random Strings. CPM (2006)
Leonid Chindelevitch, Zhentao Li, Eric Blais, Mathieu Blanchette
On the Inference of Parsimonious Indel Evolutionary Scenarios. J. Bioinform. Comput. Biol. 4 (3) (2006)