Тестирование недвижимости в других метриках?

20

Существует большое количество литературы по «тестированию свойств» - проблеме создания небольшого числа запросов черного ящика к функции чтобы различать два случая:f:{0,1}nR

  1. является членом некоторого класса функций CfC

  2. является ε -far из каждой функции в классе C .fεC

Диапазон функции иногда является логическим: R = { 0 , 1 } , но не всегда.RR={0,1}

Здесь, -far , как правило , следует понимать расстояние Хемминга: доля точек F , которые должны были бы быть изменены , с тем чтобы место F в классе C . Это естественная метрика, если f имеет логический диапазон, но кажется менее естественной, если диапазон, скажем, действительный.εffCf

Мой вопрос: существует ли часть литературы по тестированию свойств, которая проверяет близость к некоторому классу относительно других метрик?C

Аарон Рот
источник

Ответы:

19

Да, есть! Я приведу три примера:

  1. Учитывая набор S и «таблицу умножения» над S x S, рассмотрим проблему определения, описывает ли вход абелеву группу или она далека от единицы. Фридл, Иваниос и Сантха в STOC '05 показали, что есть тестер свойств с полилогом сложности запросов (| S |), когда мера расстояния соответствует расстоянию редактирования таблиц умножения, что позволяет добавлять и удалять строки и столбцы из таблица умножения. Эту проблему также рассматривали в модели расстояний Хэмминга Эргун, Каннан, Кумар, Рубинфельд и Вишванатан (JCSS '00), где они показали сложность запроса O ~ (| S | ^ {3/2}).

  2. Большой объем работы проделан по тестированию свойств графа, где графы представлены с использованием списков смежности, и существует ограничение на степень каждой вершины. В этом случае модель расстояния - это не совсем расстояние Хэмминга, а количество ребер, которые можно добавить или удалить при сохранении границы степени.

  3. В тесно связанном исследовании проверочных свойств распределений были изучены различные понятия расстояния между распределениями. В этой модели вход является распределением вероятностей по некоторому набору, и алгоритм получает к нему доступ путем выборки из набора в соответствии с неизвестным распределением. Затем алгоритм должен определить, удовлетворяет ли распределение некоторому свойству или находится «далеко» от него. Здесь были изучены различные понятия расстояния, такие как L_1, L_2, землеройная машина. Распределения вероятностей по бесконечным областям также изучались здесь ( Adamaszek-Czumaj-Sohler, SODA '10 ).

Арнаб
источник
4
Чтобы прояснить # 1, четкая (ИМХО) более естественная проблема заключается в проверке на монотонность, где расстояние - это число позиций, которые должны быть обнаружены в перестановке, чтобы сделать ее монотонной. Это было изучено в вышеупомянутой статье JCSS'00 (приведшей к самой последней статье FOCS'10 Comandur-Saks).
Алекс Андони
если это не слишком много проблем, не могли бы вы дать ссылку на документы, на которые ссылаются? в идеале версия doi / acm.
Суреш Венкат
7

Обычно это не называется тестированием свойств (и на самом деле это не так), но есть большая часть работы по определению свойств матрицы, рассматривая небольшой индуцированный минор. Это очень похоже на цель в тестировании свойств. Смотри, например, статью Рудельсона и Вершинина:

http://portal.acm.org/citation.cfm?id=1255449

Есть более ранние работы Frieze-Kannan. Дело в том, что обычно используемая ими метрика представляет собой некоторую матричную норму, такую ​​как спектральная норма, норма Фробениуса или норма отсечки. Если вы хотите, вы можете думать о некоторых из этих результатов как об алгоритмах тестирования свойств в метрике, отличной от расстояния Хэмминга.

Moritz
источник
4

f:[n]dRLpp1Lp

Lp

L1L1L1n1


Lp

k

Климент С.
источник