Theory Seminar, Wednesday Jan 08: Amit Levi (Haifa) - Testing vs Estimation for Index-Invariant Properties in the Huge Object Model

[Arnold Filtser]

Hi all,

Next week (Wed Jan 08, at 12) we will meet for our theory seminar.

Location: Building 503 room 226.

See you all there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Amit Levi (Haifa)
Title:  Testing vs Estimation for Index-Invariant Properties in the Huge Object Model
Abstract:  The Huge Object model of property testing [Goldreich and Ron, TheoretiCS 23] concerns properties of distributions supported on , where is so large that even reading a single sampled string is unrealistic. Instead, query access is provided to the samples, and the efficiency of the algorithm is measured by the total number of queries that were made to them.
  Index-invariant properties under this model were defined in [Chakraborty et al., COLT 23], as a compromise between enduring the full intricacies of string testing when considering unconstrained properties, and giving up completely on the string structure when considering label-invariant properties.
Index-invariant properties are those that are invariant through a consistent reordering of the bits of the involved strings.
  Here we provide an adaptation of Szemer\'edi's regularity method for this setting, and in particular show that if an index-invariant property admits an -test with a number of queries depending only on the proximity parameter , then it also admits a distance estimation algorithm whose number of queries depends only on the approximation parameter.

[Arnold Filtser]

This happens tomorrow!