Eric Blais

According to our database, Eric Blais authored at least 55 papers between 2006 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

New Graph and Hypergraph Container Lemmas with Applications in Property Testing.

Eric Blais, Cameron Seth

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Testing and Learning Convex Sets in the Ternary Hypercube.

Hadley Black, Eric Blais, Nathaniel Harms

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

2023

A New Minimax Theorem for Randomized Algorithms.

Shalev Ben-David, Eric Blais

J. ACM, December, 2023

Testing Convexity of Discrete Sets in High Dimensions.

Hadley Black, Eric Blais, Nathaniel Harms

CoRR, 2023

Testing Graph Properties with the Container Method.

Eric Blais, Cameron Seth

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Randomised Composition and Small-Bias Minimax.

Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre

Electron. Colloquium Comput. Complex., 2022

2021

A Polynomial Lower Bound for Testing Monotonicity.

Aleksandrs Belovs, Eric Blais

SIAM J. Comput., 2021

VC dimension and distribution-free sample-based testing.

Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

Box Covers and Domain Orderings for Beyond Worst-Case Join Processing.

Kaleb Alway, Eric Blais, Semih Salihoglu

Proceedings of the 24th International Conference on Database Theory, 2021

2020

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.

Shalev Ben-David, Eric Blais

CoRR, 2020

Testing convexity of functions over finite domains.

Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

A New Minimax Theorem for Randomized Algorithms (Extended Abstract).

Shalev Ben-David, Eric Blais

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract.

Shalev Ben-David, Eric Blais

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

On Testing and Robust Characterizations of Convexity.

Eric Blais, Abhinav Bommireddi

Proceedings of the Approximation, 2020

2019

Distribution Testing Lower Bounds via Reductions from Communication Complexity.

Eric Blais, Clément L. Canonne, Tom Gur

ACM Trans. Comput. Theory, 2019

Optimal Separation and Strong Direct Sum for Randomized Query Complexity.

Eric Blais, Joshua Brody

Proceedings of the 34th Computational Complexity Conference, 2019

2017

I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making.

Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld

Proc. VLDB Endow., 2017

Testing Submodularity and Other Properties of Valuation Functions.

Eric Blais, Abhinav Bommireddi

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization.

Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Peter van Beek

Proceedings of the Advances in Artificial Intelligence, 2017

2016

Testing Juntas and Related Properties of Boolean Functions.

Eric Blais

Encyclopedia of Algorithms, 2016

A Characterization of Constant-Sample Testable Properties.

Eric Blais, Yuichi Yoshida

Electron. Colloquium Comput. Complex., 2016

Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.).

Eric Blais, Clément Louis Canonne, Tom Gur

Electron. Colloquium Comput. Complex., 2016

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.

Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron

Electron. Colloquium Comput. Complex., 2016

A mathematical model of performance-relevant feature interactions.

Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Huiqun Yu

Proceedings of the 20th International Systems and Software Product Line Conference, 2016

Learning and Testing Junta Distributions.

Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld

Proceedings of the 29th Conference on Learning Theory, 2016

Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.

Ronitt Rubinfeld, Eric Blais

Proceedings of the Handbook of Big Data., 2016

2015

Quantum Algorithm for Monotonicity Testing on the Hypercube.

Aleksandrs Belovs, Eric Blais

Theory Comput., 2015

Partially Symmetric Functions Are Efficiently Isomorphism Testable.

Eric Blais, Amit Weinstein, Yuichi Yoshida

SIAM J. Comput., 2015

Approximating Boolean Functions with Depth-2 Circuits.

Eric Blais, Li-Yang Tan

SIAM J. Comput., 2015

Rapid Sampling for Visualizations with Ordering Guarantees.

Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld

Proc. VLDB Endow., 2015

An inequality for the Fourier spectrum of parity decision trees.

Eric Blais, Li-Yang Tan, Andrew Wan

CoRR, 2015

Performance Prediction of Configurable Software Systems by Fourier Learning (T).

Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki

Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering, 2015

2014

Learning circuits with few negations.

Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan

Electron. Colloquium Comput. Complex., 2014

Semi-Strong Colouring of Intersecting Hypergraphs.

Eric Blais, Amit Weinstein, Yuichi Yoshida

Comb. Probab. Comput., 2014

On DNF Approximators for Monotone Boolean Functions.

Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Lower Bounds for Testing Properties of Functions over Hypergrid Domains.

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

The Information Complexity of Hamming Distance.

Eric Blais, Joshua Brody, Badih Ghazi

Proceedings of the Approximation, 2014

2013

Hypercontractivity Via the Entropy Method.

Eric Blais, Li-Yang Tan

Theory Comput., 2013

Nearly Tight Bounds for Testing Function Isomorphism.

Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah

SIAM J. Comput., 2013

Lower Bounds for Testing Properties of Functions on Hypergrid Domains.

Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev

Electron. Colloquium Comput. Complex., 2013

2012

Property Testing Lower Bounds via Communication Complexity.

Eric Blais, Joshua Brody, Kevin Matulef

Comput. Complex., 2012

Active Property Testing.

Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang

Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Tight Bounds for Testing k-Linearity.

Eric Blais, Daniel M. Kane

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

2011

Active Testing

Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang

CoRR, 2011

2010

Polynomial regression under arbitrary product distributions.

Eric Blais, Ryan O'Donnell, Karl Wimmer

Mach. Learn., 2010

Testing Juntas: A Brief Survey.

Eric Blais

Proceedings of the Property Testing - Current Research and Surveys, 2010

Lower Bounds for Testing Function Isomorphism.

Eric Blais, Ryan O'Donnell

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010

Testing Boolean Function Isomorphism.

Noga Alon, Eric Blais

Proceedings of the Approximation, 2010

k⁺ Decision Trees - (Extended Abstract).

James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo

Proceedings of the Algorithms for Sensor Systems, 2010

2009

Testing juntas nearly optimally.

Eric Blais

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Improved Bounds for Testing Juntas.

Eric Blais

Proceedings of the Approximation, 2008

2007

Gene Maps Linearization Using Genomic Rearrangement Distances.

Guillaume Blin, Eric Blais, Danny Hermelin, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk

J. Comput. Biol., 2007

2006

On the Inference of Parsimonious Indel Evolutionary Scenarios.

Leonid Chindelevitch, Zhentao Li, Eric Blais, Mathieu Blanchette

J. Bioinform. Comput. Biol., 2006

Inferring Gene Orders from Gene Maps Using the Breakpoint Distance.

Guillaume Blin, Eric Blais, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk

Proceedings of the Comparative Genomics, 2006

Common Substrings in Random Strings.

Eric Blais, Mathieu Blanchette

Proceedings of the Combinatorial Pattern Matching, 17th Annual Symposium, 2006