Eric Blais

88 papers A* 16A 9B 2C 1Journal 47Unranked 9
YearRankTypeTitle / Venue / Authors
2025 A* conf
Direct Product Theorems for Randomized Query Complexity.
FOCS
Shalev Ben-David, Eric Blais
2025 J jnl
Direct Product Theorems for Randomized Query Complexity.
CoRR
Shalev Ben-David, Eric Blais
2025 J jnl
Testing Graph Properties with the Container Method.
SIAM J. Comput.
Eric Blais, Cameron Seth
2024 A* conf
New Graph and Hypergraph Container Lemmas with Applications in Property Testing.
STOC
Eric Blais, Cameron Seth
2024 J jnl
New Graph and Hypergraph Container Lemmas with Applications in Property Testing.
CoRR
Eric Blais, Cameron Seth
2024 A conf
Testing and Learning Convex Sets in the Ternary Hypercube.
ITCS
Hadley Black, Eric Blais, Nathaniel Harms
2023 J jnl
A New Minimax Theorem for Randomized Algorithms.
J. ACM
Shalev Ben-David, Eric Blais
2023 J jnl
Testing Convexity of Discrete Sets in High Dimensions.
CoRR
Hadley Black, Eric Blais, Nathaniel Harms
2023 A* conf
Testing Graph Properties with the Container Method.
FOCS
Eric Blais, Cameron Seth
2023 J jnl
Testing Graph Properties with the Container Method.
CoRR
Eric Blais, Cameron Seth
2022 A* conf
Randomised Composition and Small-Bias Minimax.
FOCS
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
2022 J jnl
Randomised Composition and Small-Bias Minimax.
CoRR
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
2022 J jnl
Randomised Composition and Small-Bias Minimax.
Electron. Colloquium Comput. Complex.
Shalev Ben-David, Eric Blais, Mika Göös, Gilbert Maystre
2021 J jnl
A Polynomial Lower Bound for Testing Monotonicity.
SIAM J. Comput.
Aleksandrs Belovs, Eric Blais
2021 A conf
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing.
ICDT
Kaleb Alway, Eric Blais, Semih Salihoglu
2021 A* conf
VC dimension and distribution-free sample-based testing.
STOC
Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
2020 A* conf
A New Minimax Theorem for Randomized Algorithms (Extended Abstract).
FOCS
Shalev Ben-David, Eric Blais
2020 J jnl
A New Minimax Theorem for Randomized Algorithms.
CoRR
Shalev Ben-David, Eric Blais
2020 J jnl
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions.
CoRR
Shalev Ben-David, Eric Blais
2020 A* conf
A Tight Composition Theorem for the Randomized Query Complexity of Partial Functions: Extended Abstract.
FOCS
Shalev Ben-David, Eric Blais
2020 — conf
On Testing and Robust Characterizations of Convexity.
APPROX-RANDOM
Eric Blais, Abhinav Bommireddi
2020 A* conf
Testing convexity of functions over finite domains.
SODA
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
2020 J jnl
VC Dimension and Distribution-Free Sample-Based Testing.
CoRR
Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
2019 J jnl
A characterization of constant-sample testable properties.
Random Struct. Algorithms
Eric Blais, Yuichi Yoshida
2019 J jnl
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing.
CoRR
Kaleb Alway, Eric Blais, Semih Salihoglu
2019 J jnl
Distribution Testing Lower Bounds via Reductions from Communication Complexity.
ACM Trans. Comput. Theory
Eric Blais, Clément L. Canonne, Tom Gur
2019 A conf
Optimal Separation and Strong Direct Sum for Randomized Query Complexity.
CCC
Eric Blais, Joshua Brody
2019 J jnl
Optimal Separation and Strong Direct Sum for Randomized Query Complexity.
CoRR
Eric Blais, Joshua Brody
2019 J jnl
Testing convexity of functions over finite domains.
CoRR
Aleksandrs Belovs, Eric Blais, Abhinav Bommireddi
2019 J jnl
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
ACM Trans. Comput. Theory
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2018 — ed.
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2018, Princeton, NJ, USA, August 20-22, 2018
APPROX-RANDOM
Eric Blais, Klaus Jansen, José D. P. Rolim, David Steurer
2018 A* conf
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
SODA
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2017 — conf
A Worst-Case Analysis of Constraint-Based Algorithms for Exact Multi-objective Combinatorial Optimization.
Canadian AI
Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Peter van Beek
2017 A conf
Distribution Testing Lower Bounds via Reductions from Communication Complexity.
CCC
Eric Blais, Clément L. Canonne, Tom Gur
2017 J jnl
I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making.
Proc. VLDB Endow.
Sajjadur Rahman, Maryam Aliakbarpour, Hidy Kong, Eric Blais, Karrie Karahalios, Aditya G. Parameswaran, Ronitt Rubinfeld
2017 A conf
Testing Submodularity and Other Properties of Valuation Functions.
ITCS
Eric Blais, Abhinav Bommireddi
2016 J jnl
A Characterization of Constant-Sample Testable Properties.
CoRR
Eric Blais, Yuichi Yoshida
2016 J jnl
A Characterization of Constant-Sample Testable Properties.
Electron. Colloquium Comput. Complex.
Eric Blais, Yuichi Yoshida
2016 B conf
A mathematical model of performance-relevant feature interactions.
SPLC
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki, Huiqun Yu
2016 A* conf
A polynomial lower bound for testing monotonicity.
STOC
Aleksandrs Belovs, Eric Blais
2016 J jnl
Alice and Bob Show Distribution Testing Lower Bounds (They don't talk to each other anymore.).
Electron. Colloquium Comput. Complex.
Eric Blais, Clément Louis Canonne, Tom Gur
2016 A* conf
Learning and Testing Junta Distributions.
COLT
Maryam Aliakbarpour, Eric Blais, Ronitt Rubinfeld
2016 — ch.
Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.
Handbook of Big Data
Ronitt Rubinfeld, Eric Blais
2016 — ch.
Testing Juntas and Related Properties of Boolean Functions.
Encyclopedia of Algorithms
Eric Blais
2016 J jnl
Testing submodularity and other properties of valuation functions.
CoRR
Eric Blais, Abhinav Bommireddi
2016 J jnl
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
CoRR
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2016 J jnl
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
Electron. Colloquium Comput. Complex.
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2015 J jnl
A Polynomial Lower Bound for Testing Monotonicity.
CoRR
Aleksandrs Belovs, Eric Blais
2015 J jnl
An inequality for the Fourier spectrum of parity decision trees.
CoRR
Eric Blais, Li-Yang Tan, Andrew Wan
2015 J jnl
Approximating Boolean Functions with Depth-2 Circuits.
SIAM J. Comput.
Eric Blais, Li-Yang Tan
2015 — conf
Learning Circuits with few Negations.
APPROX-RANDOM
Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2015 J jnl
Partially Symmetric Functions Are Efficiently Isomorphism Testable.
SIAM J. Comput.
Eric Blais, Amit Weinstein, Yuichi Yoshida
2015 A* conf
Performance Prediction of Configurable Software Systems by Fourier Learning (T).
ASE
Yi Zhang, Jianmei Guo, Eric Blais, Krzysztof Czarnecki
2015 J jnl
Quantum Algorithm for Monotonicity Testing on the Hypercube.
CoRR
Aleksandrs Belovs, Eric Blais
2015 J jnl
Quantum Algorithm for Monotonicity Testing on the Hypercube.
Theory Comput.
Aleksandrs Belovs, Eric Blais
2015 J jnl
Rapid Sampling for Visualizations with Ordering Guarantees.
Proc. VLDB Endow.
Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Samuel Madden, Ronitt Rubinfeld
2014 J jnl
Learning circuits with few negations.
CoRR
Eric Blais, Clément L. Canonne, Igor C. Oliveira, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
Learning circuits with few negations.
Electron. Colloquium Comput. Complex.
Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan
2014 A conf
Lower Bounds for Testing Properties of Functions over Hypergrid Domains.
CCC
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
2014 — conf
On DNF Approximators for Monotone Boolean Functions.
ICALP (1)
Eric Blais, Johan Håstad, Rocco A. Servedio, Li-Yang Tan
2014 J jnl
Rapid Sampling for Visualizations with Ordering Guarantees.
CoRR
Albert Kim, Eric Blais, Aditya G. Parameswaran, Piotr Indyk, Sam Madden, Ronitt Rubinfeld
2014 J jnl
Semi-Strong Colouring of Intersecting Hypergraphs.
Comb. Probab. Comput.
Eric Blais, Amit Weinstein, Yuichi Yoshida
2014 — conf
The Information Complexity of Hamming Distance.
APPROX-RANDOM
Eric Blais, Joshua Brody, Badih Ghazi
2013 A conf
Approximating Boolean Functions with Depth-2 Circuits.
CCC
Eric Blais, Li-Yang Tan
2013 J jnl
Approximating Boolean functions with depth-2 circuits.
Electron. Colloquium Comput. Complex.
Eric Blais, Li-Yang Tan
2013 J jnl
Hypercontractivity Via the Entropy Method.
Theory Comput.
Eric Blais, Li-Yang Tan
2013 J jnl
Lower Bounds for Testing Properties of Functions on Hypergrid Domains.
Electron. Colloquium Comput. Complex.
Eric Blais, Sofya Raskhodnikova, Grigory Yaroslavtsev
2013 J jnl
Nearly Tight Bounds for Testing Function Isomorphism.
SIAM J. Comput.
Noga Alon, Eric Blais, Sourav Chakraborty, David García-Soriano, Arie Matsliah
2012 A* conf
Active Property Testing.
FOCS
Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang
2012 A* conf
Partially Symmetric Functions Are Efficiently Isomorphism-Testable.
FOCS
Eric Blais, Amit Weinstein, Yuichi Yoshida
2012 J jnl
Property Testing Lower Bounds via Communication Complexity.
Comput. Complex.
Eric Blais, Joshua Brody, Kevin Matulef
2012 — conf
Tight Bounds for Testing k-Linearity.
APPROX-RANDOM
Eric Blais, Daniel M. Kane
2011 J jnl
Active Testing
CoRR
Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang
2011 J jnl
Partially Symmetric Functions are Efficiently Isomorphism-Testable
CoRR
Eric Blais, Amit Weinstein, Yuichi Yoshida
2011 A conf
Property Testing Lower Bounds via Communication Complexity.
CCC
Eric Blais, Joshua Brody, Kevin Matulef
2011 J jnl
Property Testing Lower Bounds via Communication Complexity.
Electron. Colloquium Comput. Complex.
Eric Blais, Joshua Brody, Kevin Matulef
2010 A conf
Lower Bounds for Testing Function Isomorphism.
CCC
Eric Blais, Ryan O'Donnell
2010 J jnl
Polynomial regression under arbitrary product distributions.
Mach. Learn.
Eric Blais, Ryan O'Donnell, Karl Wimmer
2010 — conf
Testing Boolean Function Isomorphism.
APPROX-RANDOM
Noga Alon, Eric Blais
2010 — ch.
Testing Juntas: A Brief Survey.
Property Testing
Eric Blais
2010 C conf
k
ALGOSENSORS
James Aspnes, Eric Blais, Murat Demirbas, Ryan O'Donnell, Atri Rudra, Steve Uurtamo
2009 A* conf
Testing juntas nearly optimally.
STOC
Eric Blais
2008 — conf
Improved Bounds for Testing Juntas.
APPROX-RANDOM
Eric Blais
2008 A* conf
Polynomial Regression under Arbitrary Product Distributions.
COLT
Eric Blais, Ryan O'Donnell, Karl Wimmer
2007 J jnl
Gene Maps Linearization Using Genomic Rearrangement Distances.
J. Comput. Biol.
Guillaume Blin, Eric Blais, Danny Hermelin, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk
2006 B conf
Common Substrings in Random Strings.
CPM
Eric Blais, Mathieu Blanchette
2006 — conf
Inferring Gene Orders from Gene Maps Using the Breakpoint Distance.
Comparative Genomics
Guillaume Blin, Eric Blais, Pierre Guillon, Mathieu Blanchette, Nadia El-Mabrouk
2006 J jnl
On the Inference of Parsimonious Indel Evolutionary Scenarios.
J. Bioinform. Comput. Biol.
Leonid Chindelevitch, Zhentao Li, Eric Blais, Mathieu Blanchette