Verwendung von XORification

18

XORification ist die Technik, um eine Boolesche Funktion oder Formel zu erschweren, indem jede Variable durch das XOR von k 2 verschiedenen Variablen x 1x k ersetzt wird . xk2x1xk

Ich bin mir bewusst, dass diese Technik bei der Komplexität von Beweisen eingesetzt wird, hauptsächlich, um Raumuntergrenzen für auflösungsbasierte Beweissysteme zu erhalten, z. B. in den Abhandlungen:

  • Eli Ben-Sasson. Größenkompromisse für die Auflösung. STOC 2002, 457-464.
  • Eli Ben-Sasson und Jakob Nordström. Raum in der Beweiskomplexität verstehen: Trennungen und Kompromisse durch Substitutionen. ICS 2011, 401-416.

Gibt es andere Anwendungen dieser Technik in anderen Bereichen?

Jan Johannsen
quelle

Antworten:

15

Hier ist ein etwas relevantes Beispiel, das wir derzeit in meiner Klasse behandeln.

Die "Speicherzugriffsfunktion" ist für Bits definiert als:2k+k

SA(x1,...,x2k,a1,...,ak)=xbin(a1ak)

Dabei ist die eindeutige Ganzzahl in { 1 , , 2 k } , die der Zeichenfolge a 1 entsprichtbin(a1ak){1,,2k}a1ak

SAO(k2k)2kkai1 an jedem Eingang . Dann UND jedes Bitxi mit dem Ausgang der entsprechenden Gruppe, dann ODER alle diese Ausgänge.

2k+123k Formeln mit einer Größe von über AND / OR / NOT:

SA(x1,...,x2k,j=12k/ka1,j,...,j=12k/kak,j)=xbin(a1ak).

This is often called "Andreev's function" in the literature. Hastad proved (improving a component of Andreev's argument) that cubic-size formulas are essentially necessary. (It is not hard to find nearly cubic-size formulas for it, too.)

Ryan Williams
quelle
Thanks Ryan, that's exactly the kind of thing I was looking for.
Jan Johannsen
13

This might be a slight reach, but the idea of XOR'ing a bunch of things to make a task "harder" shows up in cryptography. It first appeared in the guise of Yao's XOR lemma. If X is a slightly unpredictable random variable, then Y=X1X2Xk is extremely unpredictable if k is large enough, where the Xi's are independent draws of X.

Nowadays, this technique is quite standard in crypto, typically for amplifying a weak construction (commitment scheme, oblivious transfer protocol, etc) into a strong one.

mikero
quelle
5
To complement this post: XOR lemmas are everywhere. Eg, see this paper and its references: theoryofcomputing.org/articles/v004a007
MCH
2
The XOR lemma is different from what I look for: here a k-ary parity gate is added at the output, with k copies of the function fed into it. XORification on the other hand adds a k-ary parity gate at each input, with k new variables fed into it.
Jan Johannsen