Abstract We study the approximation of halfspaces $$h:\{0,1\}^n\to\{0,1\}$$ h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus $$2^{-\Omega(n)}$$ 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus $$\Omega(n)$$ Ω ( n ) between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k-party number-on-the-forehead model, where we obtain an explicit separation of log n versus $$\Omega(n/4^{n})$$ Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.

arXiv:1902.01765Computational ComplexityAug 3, 20213 citations

Quantumness and Irrationality

Alexandr Alexandrovich Ezhov, Andrei G. Khromov, Svetlana S. Terentyeva

Studies in computational intelligenceOct 5, 20181 citation

Springer eBooks

Classical Versus Quantum Rationality

Andrei Yu. Khrennikov

Published Jan 1, 2023• 0 citations

Publisher

DOI: 10.1007/978-3-031-29024-4_3

Related papers

From Classical Rationality to Quantum Cognition

Pierre Uzan

Lecture notes in computer scienceJan 1, 20240 citations

The quantum-like approach to modeling classical rationality violations: an introduction

Franco Vaio

Mind & SocietyApr 25, 20194 citations

Quantum versus classical uncertainty

Shunlong Luo

Theoretical and Mathematical PhysicsMay 1, 2005149 citations

IMMANENT POWERS VERSUS CAUSAL POWERS (PROPENSITIES, LATENCIES AND DISPOSITIONS) IN QUANTUM MECHANICS

Christian DE RONDE

In this paper we compare two different notions of 'power', both of which attempt to provide a realist understanding of quantum mechanics grounded on the potential mode of existence. For this propose we will begin by introducing two different notions of potentiality present already within Aristotelian metaphysics, namely, irrational potentiality and rational potentiality. After discussing the role played by potentiality within classical and quantum mechanics, we will address the notion of causal power which is directly related to irrational potentiality and has been adopted by many interpretations of QM. We will then present the notion of immanent power which relates to rational potentiality and argue that this new concept presents important advantages regarding the possibilities it provides for understanding in a novel manner the theory of quanta. We end our paper with a comparison between both notions of 'power', stressing some radical differences between them.In this paper we compare two different notions of 'power', both of which attempt to provide a realist understanding of quantum mechanics grounded on the potential mode of existence. For this propose we will begin by introducing two different notions of potentiality present already within Aristotelian metaphysics, namely, irrational potentiality and rational potentiality. After discussing the role played by potentiality within classical and quantum mechanics, we will address the notion of causal power which is directly related to irrational potentiality and has been adopted by many interpretations of QM. We will then present the notion of immanent power which relates to rational potentiality and argue that this new concept presents important advantages regarding the possibilities it provides for understanding in a novel manner the theory of quanta. We end our paper with a comparison between both notions of 'power', stressing some radical differences between them.

arXiv:1711.02997Nov 20, 201813 citations

The hardest halfspace

Alexander A. Sherstov

Abstract We study the approximation of halfspaces $h:\{0,1\}^n\to\{0,1\}$ h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus $2^{-\Omega(n)}$ 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus $\Omega(n)$ Ω ( n ) between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k-party number-on-the-forehead model, where we obtain an explicit separation of log n versus $\Omega(n/4^{n})$ Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.Abstract We study the approximation of halfspaces $$h:\{0,1\}^n\to\{0,1\}$$ h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus $$2^{-\Omega(n)}$$ 2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus $$\Omega(n)$$ Ω ( n ) between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k-party number-on-the-forehead model, where we obtain an explicit separation of log n versus $$\Omega(n/4^{n})$$ Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.

arXiv:1902.01765Computational ComplexityAug 3, 20213 citations

Quantumness and Irrationality

Alexandr Alexandrovich Ezhov, Andrei G. Khromov, Svetlana S. Terentyeva

Studies in computational intelligenceOct 5, 20181 citation

Abstract We study the approximation of halfspaces

h:\{0,1\}^n\to\{0,1\}

h : { 0 , 1 } n → { 0 , 1 } in the infinity norm by polynomials and rational functions of any given degree. Our main result is an explicit construction of the “hardest” halfspace, for which we prove polynomial and rational approximation lower bounds that match the trivial upper bounds achievable for all halfspaces. This completes a lengthy line of work started by Myhill and Kautz (1961). As an application, we construct a communication problem that achieves essentially the largest possible separation, of O(n) versus

2^{-\Omega(n)}

2 - Ω ( n ) , between the sign-rank and discrepancy. Equivalently, our problem exhibits a gap of log n versus

\Omega(n)

Ω ( n ) between the communication complexity with unbounded versus weakly unbounded error, improving quadratically on previous constructions and completing a line of work started by Babai, Frankl, and Simon (FOCS 1986). Our results further generalize to the k-party number-on-the-forehead model, where we obtain an explicit separation of log n versus

\Omega(n/4^{n})

Ω ( n / 4 n ) for communication with unbounded versus weakly unbounded error.