Eric Blais

According to our database1, Eric Blais authored at least 44 papers between 2006 and 2020.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.



In proceedings 
PhD thesis 




Testing convexity of functions over finite domains.
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Distribution Testing Lower Bounds via Reductions from Communication Complexity.
TOCT, 2019

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

Optimal Separation and Strong Direct Sum for Randomized Query Complexity.
Proceedings of the 34th Computational Complexity Conference, 2019

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

Testing Submodularity and Other Properties of Valuation Functions.
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.
Proceedings of the Advances in Artificial Intelligence, 2017

Testing Juntas and Related Properties of Boolean Functions.
Encyclopedia of Algorithms, 2016

A Characterization of Constant-Sample Testable Properties.
Electronic Colloquium on Computational Complexity (ECCC), 2016

Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.).
Electronic Colloquium on Computational Complexity (ECCC), 2016

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
Electronic Colloquium on Computational Complexity (ECCC), 2016

A polynomial lower bound for testing monotonicity.
Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 2016

A mathematical model of performance-relevant feature interactions.
Proceedings of the 20th International Systems and Software Product Line Conference, 2016

Learning and Testing Junta Distributions.
Proceedings of the 29th Conference on Learning Theory, 2016

Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.
Proceedings of the Handbook of Big Data., 2016

Quantum Algorithm for Monotonicity Testing on the Hypercube.
Theory of Computing, 2015

Partially Symmetric Functions Are Efficiently Isomorphism Testable.
SIAM J. Comput., 2015

Rapid Sampling for Visualizations with Ordering Guarantees.
PVLDB, 2015

An inequality for the Fourier spectrum of parity decision trees.
CoRR, 2015

Performance Prediction of Configurable Software Systems by Fourier Learning (T).
Proceedings of the 30th IEEE/ACM International Conference on Automated Software Engineering, 2015

Learning circuits with few negations.
Electronic Colloquium on Computational Complexity (ECCC), 2014

Semi-Strong Colouring of Intersecting Hypergraphs.
Combinatorics, Probability & Computing, 2014

On DNF Approximators for Monotone Boolean Functions.
Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Lower Bounds for Testing Properties of Functions over Hypergrid Domains.
Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

The Information Complexity of Hamming Distance.
Proceedings of the Approximation, 2014

Hypercontractivity Via the Entropy Method.
Theory of Computing, 2013

Nearly Tight Bounds for Testing Function Isomorphism.
SIAM J. Comput., 2013

Approximating Boolean functions with depth-2 circuits.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Lower Bounds for Testing Properties of Functions on Hypergrid Domains.
Electronic Colloquium on Computational Complexity (ECCC), 2013

Property Testing Lower Bounds via Communication Complexity.
Computational Complexity, 2012

Active Property Testing.
Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science, 2012

Tight Bounds for Testing k-Linearity.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2012

Active Testing
CoRR, 2011

Polynomial regression under arbitrary product distributions.
Machine Learning, 2010

Testing Juntas: A Brief Survey.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Lower Bounds for Testing Function Isomorphism.
Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010

Testing Boolean Function Isomorphism.
Proceedings of the Approximation, 2010

k + Decision Trees - (Extended Abstract).
Proceedings of the Algorithms for Sensor Systems, 2010

Testing juntas nearly optimally.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Improved Bounds for Testing Juntas.
Proceedings of the Approximation, 2008

Gene Maps Linearization Using Genomic Rearrangement Distances.
Journal of Computational Biology, 2007

On the Inference of Parsimonious Indel Evolutionary Scenarios.
J. Bioinformatics and Computational Biology, 2006

Inferring Gene Orders from Gene Maps Using the Breakpoint Distance.
Proceedings of the Comparative Genomics, 2006

Common Substrings in Random Strings.
Proceedings of the Combinatorial Pattern Matching, 17th Annual Symposium, 2006