Key points are not available for this paper at this time.
Le problème d'évitement de plage (désigné par Avoid) consiste à trouver une chaîne en dehors de la plage d'un circuit donné C : 0, 1n→0, 1m, où m>n. Bien qu'au moins la moitié des chaînes de longueur m soient des réponses correctes, il n'est pas clair comment en trouver une de manière déterministe. Des résultats récents de Korten (FOCS'21) et de Ren, Wang et Santhanam (FOCS'22) montrent que des algorithmes déterministes efficaces pour Avoid auraient des conséquences de grande portée, y compris des limites inférieures solides pour les circuits et des constructions explicites d'objets combinatoires (par exemple, graphes de Ramsey, extracteurs, matrices rigides). Cela motive fortement la question : existe-t-il réellement un algorithme déterministe efficace pour Avoid ?
Ilango et al. (Tue,) ont étudié cette question.