Eric Blais

activity

20092026

most citedLongest Common Subsequences in Sets of Permutations

13 citations · 25 across the 15 of their papers we have counts for

collaborators

Showing 2016Show all

3 papers · 1 filter

cs.DS2016

A Characterization of Constant-Sample Testable Properties

Eric Blais, Yuichi Yoshida

We characterize the set of properties of Boolean-valued functions on a finite domain $X$ that are testable with a constant number of samples. Specifically, we show that a…

cs.DS2016★ 1 cited

Testing submodularity and other properties of valuation functions

Eric Blais, Abhinav Bommireddi

We show that for any constant $ε > 0$ and $p \geq 1$ , it is possible to distinguish functions $f : {0, 1}^{n} \to [0, 1]$ that are submodular from those that are $ε$ -far from every sub…

cs.DS2016

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

Eric Blais, Clément L. Canonne, Talya Eden +2

A function $f : {- 1, 1}^{n} \to {- 1, 1}$ is a $k$ -junta if it depends on at most $k$ of its variables. We consider the problem of tolerant testing of $k$ -juntas, where the test…