Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR23-002 | 22nd January 2023 23:40

Diagonalization Games

RSS-Feed




Revision #2
Authors: Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
Accepted on: 22nd January 2023 23:40
Downloads: 29
Keywords: 


Abstract:

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even referred to him as a ``scientific charlatan''.

In the game Kronecker maintains a list of m binary vectors,
each of length n, and Cantor's goal is to produce a new binary vector which is different from each of Kronecker's vectors, or prove that no such vector exists. Cantor does not see Kronecker's vectors but he is allowed to ask queries of the form ``What is bit number j of vector number i? What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries \emph{adaptively}, based on Kronecker's previous replies?

The case when m=n is solved by diagonalization using n (non-adaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the non-adaptive case.



Changes to previous version:

Added acks


Revision #1 to TR23-002 | 19th January 2023 11:11

Diagonalization Games





Revision #1
Authors: Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
Accepted on: 19th January 2023 11:11
Downloads: 15
Keywords: 


Abstract:

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even referred to him as a ``scientific charlatan''.

In the game Kronecker maintains a list of m binary vectors,
each of length n, and Cantor's goal is to produce a new binary vector which is different from each of Kronecker's vectors, or prove that no such vector exists. Cantor does not see Kronecker's vectors but he is allowed to ask queries of the form ``What is bit number j of vector number i? What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries \emph{adaptively}, based on Kronecker's previous replies?

The case when m=n is solved by diagonalization using n (non-adaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the non-adaptive case.



Changes to previous version:

Added references to related work


Paper:

TR23-002 | 5th January 2023 08:14

Diagonalization Games





TR23-002
Authors: Noga Alon, Olivier Bousquet, Kasper Green Larsen, Shay Moran, Shlomo Moran
Publication: 8th January 2023 04:36
Downloads: 176
Keywords: 


Abstract:

We study several variants of a combinatorial game which is based on Cantor's diagonal argument. The game is between two players called Kronecker and Cantor. The names of the players are motivated by the known fact that Leopold Kronecker did not appreciate Georg Cantor's arguments about the infinite, and even referred to him as a ``scientific charlatan''.

In the game Kronecker maintains a list of m binary vectors,
each of length n, and Cantor's goal is to produce a new binary vector which is different from each of Kronecker's vectors, or prove that no such vector exists. Cantor does not see Kronecker's vectors but he is allowed to ask queries of the form ``What is bit number j of vector number i? What is the minimal number of queries with which Cantor can achieve his goal? How much better can Cantor do if he is allowed to pick his queries \emph{adaptively}, based on Kronecker's previous replies?

The case when m=n is solved by diagonalization using n (non-adaptive) queries. We study this game more generally, and prove an optimal bound in the adaptive case and nearly tight upper and lower bounds in the non-adaptive case.



ISSN 1433-8092 | Imprint