Хороша експозиція методу випадкового обмеження

Мені цікаво, чи є хороші посилання, які описують метод випадкового обмеження як техніку нижньої межі? Я усвідомлюю, що це пов'язано з леммою перемикання і відображається у багатьох різних доказах, але я шукаю більш-менш самодостатне пояснення цієї ідеї.

5

1 Відповіді

Відносно простий параметр, який ілюструє метод випадкових обмежень, є оригінальним застосуванням Субботовської методу для доведення нижньої межі $ \ Omega (n ^ (1.5)) $ до розміру формули функції парності, де формули використовують артикль-2 AND і ОР операцій. Розділ 6.3. Функціональна складність Юкни має приємну експозицію. Також див. Ці лекції від класу Swastik Kopparty в Rutgers.

9
додано