Lower bounds for testing properties of functions over hypergrid domains
E Blais, S Raskhodnikova… - 2014 IEEE 29th …, 2014 - ieeexplore.ieee.org
We show how the communication complexity method introduced in (Blais, Brody, Matulef
2012) can be used to prove lower bounds on the number of queries required to test …
2012) can be used to prove lower bounds on the number of queries required to test …
Sequential measurements, disturbance and property testing
AW Harrow, CYY Lin, A Montanaro - Proceedings of the Twenty-Eighth Annual …, 2017 - SIAM
We describe two procedures which, given access to one copy of a quantum state and a
sequence of two-outcome measurements, can distinguish between the case that at least one …
sequence of two-outcome measurements, can distinguish between the case that at least one …
A unified framework for testing linear‐invariant properties
A Bhattacharyya, E Grigorescu… - Random Structures & …, 2015 - Wiley Online Library
In the study of property testing, a particularly important role has been played by linear
invariant properties, ie, properties of Boolean functions on the hypercube which are closed …
invariant properties, ie, properties of Boolean functions on the hypercube which are closed …
[HTML][HTML] Polynomial-time algorithms for quadratic isomorphism of polynomials: The regular case
J Berthomieu, JC Faugere, L Perret - Journal of Complexity, 2015 - Elsevier
Abstract Let f=(f 1,…, fm) and g=(g 1,…, gm) be two sets of m≥ 1 nonlinear polynomials in K
[x 1,…, xn](K being a field). We consider the computational problem of finding–if any–an …
[x 1,…, xn](K being a field). We consider the computational problem of finding–if any–an …
Property testing bounds for linear and quadratic functions via parity decision trees
A Bhrushundi, S Chakraborty, R Kulkarni - … June 7-11, 2014. Proceedings 9, 2014 - Springer
In this paper, we study linear and quadratic Boolean functions in the context of property
testing. We do this by observing that the query complexity of testing properties of linear and …
testing. We do this by observing that the query complexity of testing properties of linear and …
[PDF][PDF] Polynomial-time algorithms for quadratic isomorphism of polynomials
J Berthomieu, J Faugere, L Perret - CoRR, abs/1307.4974, 2013 - inria.hal.science
A fundamental question in computer science is to provide algorithms allowing to test if two
given objects are equivalent with respect to some transformation. In this paper, we consider …
given objects are equivalent with respect to some transformation. In this paper, we consider …