enter search term and/or author name
Exploring the Subexponential Complexity of Completion Problems
Pål Grønås Drange, Fedor V. Fomin, Michał Pilipczuk, Yngve Villanger
Article No.: 14
Let F be a family of graphs. In the F-C
We introduce quantum XOR games, a model of two-player, one-round games that extends the model of XOR games by allowing the referee’s questions to the players to be quantum states. We give examples showing that quantum XOR games exhibit a...
Input-Oblivious Proof Systems and a Uniform Complexity Perspective on P/poly
Oded Goldreich, Or Meir
Article No.: 16
An input-oblivious proof system is a proof system in which the proof does not depend on the claim being proved. Input-oblivious versions of NP and MA were introduced in passing by Fortnow, Santhanam, and Williams, who also showed...
An index e in a numbering of partial-recursive functions is called minimal if every lesser index computes a different function from e. Since the 1960s, it has been known that, in any reasonable programming language, no effective...