Hypothesis of Aander – Carp – Rosenberg

Unsolved computer science problems : Prove or refute the Aander – Karp – Rosenberg hypothesis.

The Aander – Karp – Rosenberg hypothesis (also known as the Aander – Rosenberg hypothesis or the difficulty hypothesis ) is a group of related hypotheses about the number of questions in the form “Is there an edge between the vertex u and the vertex v ?”, Which must be answered to determine if or not, an undirected graph by a certain property (invariant), such as planarity or bipartite . The hypothesis is named after the Norwegian mathematician Stoll Aander and the American scientists Richard M. Karp and Arnold L. Rosenberg. According to the hypothesis, for a wide class of invariants, no algorithm can guarantee that an algorithm can omit any query - any algorithm for determining whether a graph has the property, no matter how smart this algorithm is, it must check each pair of vertices before giving an answer. A property that satisfies a hypothesis is called .

More precisely, the Aander – Rosenberg conjecture states that any deterministic algorithm must check at least a fixed fraction of all possible pairs of vertices in order to determine in the any nontrivial monotonic property of a graph. In this context, a property is monotonic if it remains true when edges are added (so the planarity property is not monotonic, but non-planarity is monotonic). A more rigorous version of this hypothesis, called the difficulty hypothesis or the Aander – Karp – Rosenberg hypothesis, states that what is needed is exactly ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ checks. Versions of the problem for probabilistic and quantum algorithms were formulated and studied.

The deterministic Aander – Rosenberg hypothesis was proved by Rivest and Willemine ^[1] , but the stronger hypothesis by the Aander – Karp – Rosenberg hypothesis remains unproven. In addition, there is a big difference between the lower bound and the best proven lower bound for probabilistic and quantum complexity in terms of the number of queries.

Content

Example

The property of not being empty (that is, having at least one edge) is monotonous, since adding another edge to a nonempty graph gives a nonempty graph. There is a simple algorithm for testing whether a graph is not empty — loop through all pairs of vertices and check if each pair is connected by an edge. If the edge is found in this way, we break the cycle and report that the graph is not empty, and if the cycle ends without finding any edge, then report that the graph is empty. On such graphs (for example, complete graphs ), this algorithm completes quickly without checking each pair of vertices, but on an empty graph, the algorithm checks all possible pairs before it completes. Therefore, the complexity of the query algorithm is ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ - in the worst case, the algorithm does ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ checks.

The algorithm described above is not the only possible method for checking nonemptiness, but it follows from the Aander – Karp – Rosenberg hypothesis that any determinant algorithm for testing nonemptiness has the same complexity for queries ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ . That is, the property of being non-empty is difficult . For this property, the result is simply checked directly - if the algorithm fails ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ checks, he will not be able to distinguish an empty graph from a graph containing one edge of an unchecked pair of vertices and must give an incorrect answer for one of these two graphs (either for an empty or for a graph with an edge).

Definitions

In the context of this article, all graphs will be simple and non-oriented , unless otherwise stated. This means that the edges of the graph form a set (but not a multiset ) and the ends of each edge are a pair of different vertices. It is assumed that the graphs have an in which each vertex has a unique identifier or label and in which you can check the adjacency of two vertices, but in the graph to check the adjacency you can only perform basic operations.

Informally, a graph property (or graph invariant, both terms in this article are used synonymously) is a graph property that is independent of the markup. More formally, a graph property is a mapping from the set of all graphs to {0,1} so that isomorphic graphs map to the same value. For example, the property to contain at least one vertex of degree 2 is an invariant of the graph, but the property that the first vertex is of degree 2 is not an invariant of the graph, since the property depends on the layout of the graph (in particular, it depends on which vertex is considered “the first "). An invariant of a graph is called nontrivial if it does not have the same value for all graphs. For example, the property of being a graph is a trivial property, since all graphs have this property. But on the other hand, the property of being empty is not trivial, since an empty graph has this property, but a non-empty one does not. A graph property is said to be monotonous if adding edges does not destroy the property. Alternatively, if a graph has a monotone property, then any supergraph of this graph on the same set of vertices also has this property. For example, the property of being unplanar is monotonous - a supergraph of an unplanar graph is also unplanar. However, the ability to be regular is not monotonous.

For query complexity, the “O” notation is often used large . Briefly, f ( n ) is $O(g(n))$ ${\ displaystyle O (g (n))}$ if for any sufficiently large $nf(n)\leqslant cg(n)$ ${\ displaystyle nf (n) \ leqslant cg (n)}$ for some positive constant c . Similarly, f ( n ) is $\Omega (g(n))$ ${\ displaystyle \ Omega (g (n))}$ if for large enough $nf(n)\geqslant cg(n)$ ${\ displaystyle nf (n) \ geqslant cg (n)}$ for some positive constant c . Finally, f ( n ) is $\Theta (g(n))$ ${\ displaystyle \ Theta (g (n))}$ if she is like $O(g(n))$ ${\ displaystyle O (g (n))}$ so $\Omega (g(n))$ ${\ displaystyle \ Omega (g (n))}$ .

Request Complexity

The complexity of a deterministic request for computing a function of n bits $(x_{1},x_{2},\dots ,x_{n})$ ${\ displaystyle (x_ {1}, x_ {2}, \ dots, x_ {n})}$ equal to the number of bits x _i that the deterministic algorithm must read in the worst case to determine the value of the function. For example, if the function takes the value 0, if all the bits are 0 and the value 1 otherwise (that is, the OR function), then the complexity of the deterministic queries is exactly n . In the worst case, the first n - 1 bits read will be 0 and the function value will depend only on the last bit. If the algorithm does not read this bit, it may give an incorrect answer. The number of bits read is also called the number of requests made at the input. You can imagine that the algorithm asks (makes a request) the input about a specific bit and the input responds to this request.

The complexity of a probabilistic request to execute a function is defined similarly, except that the algorithm can be probabilistic, that is, it can flip a coin and use the dropped value of the side of the coin to decide which bit to request. However, the probabilistic algorithm should continue to give correct answers to all input requests - errors are unacceptable. Such algorithms are called Las Vegas algorithms and should be distinguished from Monte Carlo algorithms in which some errors are valid. The complexity of a probabilistic query can be defined in the Monte Carlo sense, but the Aander – Karp – Rosenberg hypothesis speaks of the complexity of queries for graph invariants in the sense of Las Vegas.

The quantum complexity of queries is a natural generalization of the complexity of a probabilistic query, of course, with the resolution of quantum queries and responses. The quantum complexity of queries can also be defined in the sense of Monte Carlo algorithms or Las Vegas algorithms, but quantum Monte Carlo algorithms are usually meant.

In the context of this hypothesis, the calculated function is a graph property, and the input is a string of size ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ , which sets the location of edges on a graph with n vertices, since the graph can have a maximum ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ ribs. The complexity of the request of any function is limited by the value above. ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ since all input will be read after ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ queries, which determines the entire input graph.

Complexity of deterministic queries

For deterministic algorithms, Rosenberg ^[2] suggested that for all nontrivial properties of graphs on n vertices, the decision whether a graph possesses this property requires $\Omega (n^{2})$ ${\ displaystyle \ Omega (n ^ {2})}$ queries. It is clear that the condition is required to be non-trivial, since there are trivial properties such as “is this a graph?” That can be answered without any request whatsoever.

Scorpion Earl. One of the three red vertices is adjacent to all vertices that do not belong to this path, while the other two vertices of the path are adjacent only to the vertices of the path.

The hypothesis was refuted by Aander, who proposed the property of a directed graph (the property of having a “sink”), the verification of which requires only O ( n ) queries. A sink in an oriented graph is a vertex that has an incoming half-degree n -1 and an outgoing half-degree 0 ^[3] . This property can be verified in less than 3 n queries ^[4] . The property of an undirected graph that can be checked for O ( n ) queries is the property “the graph is a scorpion graph”, first described in an article by Best, van Emde Boaz, and Lenstra ^[4] . A scorpion graph is a graph containing a path consisting of three vertices, such that one end vertex of the path is connected to all other vertices of the graph, while the two remaining vertices of the path are connected only to the vertices of the path itself.

Then Aander and Rosenberg formulated a new hypothesis (the Aander-Rosenberg hypothesis), which states that the decision whether a graph has a nontrivial monotonic property requires $\Omega (n^{2})$ ${\ displaystyle \ Omega (n ^ {2})}$ queries ^[5] . This hypothesis was decided by Rayvest and Vuyeman ^[1] , showing that at least ${\tfrac {n^{2}}{16}}$ ${\ displaystyle {\ tfrac {n ^ {2}} {16}}}$ queries to check for any non-trivial monotonic property. The border was later improved to ${\tfrac {n^{2}}{9}}$ ${\ displaystyle {\ tfrac {n ^ {2}} {9}}}$ Kleitman and Kwiatkowski ^[6] , then to ${\tfrac {n^{2}}{4}}-o(n^{2})$ ${\ displaystyle {\ tfrac {n ^ {2}} {4}} - o (n ^ {2})}$ Kahn, Sachs and Stertevant ^[7] , until ${\tfrac {8}{25}}n^{2}-o(n^{2})$ ${\ displaystyle {\ tfrac {8} {25}} n ^ {2} -o (n ^ {2})}$ Kornefel and Trish ^[8] and up ${\tfrac {n^{2}}{3}}-o(n^{2})$ ${\ displaystyle {\ tfrac {n ^ {2}} {3}} - o (n ^ {2})}$ Scheiderweiler and Trish ^[9] .

Richard Karp made a more rigorous statement (now called the difficulty hypothesis or the Aander – Karp – Rosenberg hypothesis ) that “any nontrivial monotone property of graphs on n vertices is difficult” ^[10] . A property is called difficult if determining whether the graph possesses this property requires ${\tfrac {n(n-1)}{2}}$ ${\ displaystyle {\ tfrac {n (n-1)} {2}}}$ queries ^[11] . This hypothesis states that the best testing algorithm for any non-trivial monotonic property should (in the worst case) request all possible edges. This hypothesis remains open, although it has been shown that some special properties of graphs are difficult for all n . The hypothesis was solved for the case when n is a prime power by Kahn, Sachs and Stertevant ^[7] using the topological approach. The hypothesis was solved for all non-trivial monotone properties of bipartite graphs Yao ^[12] . It was also proved that properties closed with respect to minors are also difficult for large n ^[13] .

Probability Query Complexity

Richard Karp also hypothesized that $\Omega (n^{2})$ ${\ displaystyle \ Omega (n ^ {2})}$ queries are required to verify non-trivial monotonicity properties, even if probabilistic algorithms are allowed. No nontrivial property is known that requires less ${\tfrac {n^{2}}{4}}$ ${\ displaystyle {\ tfrac {n ^ {2}} {4}}}$ requests for verification. Linear lower bound (i.e. $\Omega (n))$ ${\ displaystyle \ Omega (n))}$ for all monotonic properties, it follows from a very general . The first superlinear lower one for all monotone invariants was given by Yao ^[14] , who showed what is required $\Omega (n\log ^{\tfrac {1}{12}}n)$ ${\ displaystyle \ Omega (n \ log ^ {\ tfrac {1} {12}} n)}$ queries. She was then upgraded by King ^[15] to $\Omega (n^{\tfrac {5}{4}})$ ${\ displaystyle \ Omega (n ^ {\ tfrac {5} {4}})}$ and then Hainal ^[16] to $\Omega (n^{\tfrac {4}{3}})$ ${\ displaystyle \ Omega (n ^ {\ tfrac {4} {3}})}$ . This result was then improved to the current well-known boundary value. $\Omega (n^{\tfrac {4}{3}}\log ^{\tfrac {1}{3}}n)$ ${\ displaystyle \ Omega (n ^ {\ tfrac {4} {3}} \ log ^ {\ tfrac {1} {3}} n)}$ Chakrabarti and Hot ^[17] .

Some recent results give lower bounds, which are determined by the critical probability p of the monotonic property of the graph in question. The critical probability p is defined as the only p , such that the random graph G ( n , p ) has this property with a probability of 1/2. The random graph G ( n , p ) is a graph with n vertices in which each edge is present with probability p and the presence / absence of an edge does not depend on all other edges. Friedgood, Kahn, and Wigderson ^[18] showed that any monotone invariant of a graph with critical probability p requires $\Omega \left(\min \left\{{\frac {n}{\min(p,1-p)}},{\frac {n^{2}}{\log n}}\right\}\right)$ ${\ displaystyle \ Omega \ left (\ min \ left \ {{\ frac {n} {\ min (p, 1-p)}}, {\ frac {n ^ {2}} {\ log n}} \ right \} \ right)}$ queries. For the same problem, O'Donnell, Sachs, Schramm, and Cenedio ^[19] showed a lower bound $\Omega ({\frac {n^{\tfrac {4}{3}}}{p^{\tfrac {1}{3}}}})$ ${\ displaystyle \ Omega ({\ frac {n ^ {\ tfrac {4} {3}}} {p ^ {\ tfrac {1} {3}}}}}$ .

As in the deterministic case, there are many special invariants for which the lower bound $\Omega (n^{2})$ ${\ displaystyle \ Omega (n ^ {2})}$ known. Moreover, better bounds are known for some classes of graph invariants. For example, to check if a graph has a subgraph isomorphic to some given graph (the so-called search problem for an isomorphic subgraph ), according to Gröger, the best known lower bound is $\Omega (n^{\tfrac {3}{2}})$ ${\ displaystyle \ Omega (n ^ {\ tfrac {3} {2}})}$ ^[20] .

Quantum Query Complexity

For a uniformly limited error of the best known lower bound is $\Omega (n^{\tfrac {2}{3}}\log ^{\tfrac {1}{6}}n)$ ${\ displaystyle \ Omega (n ^ {\ tfrac {2} {3}} \ log ^ {\ tfrac {1} {6}} n)}$ as noted by Andrew Yao ^[21] . The boundary is obtained by combining the probabilistic lower bound with the quantum adversary method. The best lower bound that one hopes to achieve is $\Omega (n)$ ${\ displaystyle \ Omega (n)}$ , unlike the classical case, in view of the Grover algorithm , which gives an algorithm with O ( n ) queries for checking the monotonic nonemptiness property. Similar to the deterministic and probabilistic cases, there are some properties that are known to have a lower bound $\Omega (n)$ ${\ displaystyle \ Omega (n)}$ , for example, nonemptiness (which follows from the optimality of the Grover algorithm) and the property to contain a trogolnik . There are some invariants of the graph for which it is known that they have a lower bound $\Omega (n^{\tfrac {3}{2}})$ ${\ displaystyle \ Omega (n ^ {\ tfrac {3} {2}})}$ , and there are even properties with a lower border $\Omega (n^{2})$ ${\ displaystyle \ Omega (n ^ {2})}$ . For example, the monotonic property of non-planarity requires $\Theta (n{\tfrac {3}{2}})$ ${\ displaystyle \ Theta (n {\ tfrac {3} {2}})}$ queries ^[22] , and the monotonous properties contain more than half of the possible edges (which is also called the majority function) requires $\Theta (n^{2})$ ${\ displaystyle \ Theta (n ^ {2})}$ queries ^[23] .

Notes

↑ ¹ ² Rivest, Vuillemin, 1975 .
↑ Rosenberg, 1973 .
↑ This definition of runoff is different from the usual definition of runoff. In this definition, it is assumed that all arcs of the graph enter one vertex (sink), and in the usual definition, it is only assumed that there are no outgoing arcs from the drain (see “ Types of graph vertices ”).
↑ ¹ ² Best, van Emde Boas, Lenstra, 1974 .
↑ Triesch, 1996 .
↑ Kleitman, Kwiatkowski, 1980 .
↑ ¹ ² Kahn, Saks, Sturtevant, 1983 .
↑ Korneffel, Triesch, 2010 .
↑ Scheidweiler, Triesch, 2013 .
↑ Lutz, 2001 .
↑ Kozlov, 2008 , с. 226-228.
↑ Yao, 1988 .
↑ Chakrabarti, Khot, Shi, 2001 .
↑ Yao, 1991 .
↑ King, 1988 .
↑ Hajnal, 1991 .
↑ Chakrabarti, Khot, 2001 .
↑ Friedgut, Kahn, Wigderson, 2002 .
↑ O'Donnell, Saks, Schramm, Servedio, 2005 .
↑ Gröger, 1992 .
↑ Результат не опубликован, но упомянут в статье Magniez, Santha & Szegedy (2005 )
↑ Ambainis, Iwama, Nakanishi, Nishimura и др., 2008 .
↑ Beals, Buhrman, Cleve, Mosca, de Wolf, 2001 .

Literature

Andris Ambainis, Kazuo Iwama, Masaki Nakanishi, Harumichi Nishimura, Rudy Raymond, Seiichiro Tani, Shigeru Yamashita. Quantum query complexity of Boolean functions with small on-sets // Proceedings of the 19th International Symposium on Algorithms and Computation. — Gold Coast, Australia: Springer-Verlag , 2008. — Т. 5369. — С. 907–918. — (Lecture Notes in Computer Science). — ISBN 978-3-540-92181-3 . — DOI : 10.1007/978-3-540-92182-0_79 . .
Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, Ronald de Wolf. Quantum lower bounds by polynomials // Journal of the ACM . — 2001. — Т. 48 , вып. 4 . — С. 778–797 . — DOI : 10.1145/502090.502097 . — arXiv : quant-ph/9802049 . .
Best MR, van Emde Boas P., Lenstra HW A sharpened version of the Aanderaa-Rosenberg conjecture. — Mathematisch Centrum Amsterdam , 1974. — (Report ZW 30/74).
Amit Chakrabarti, Subhash Khot . Improved Lower Bounds on the Randomized Complexity of Graph Properties // Proceedings of the 28th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 2001. — Т. 2076. — С. 285–296. — (Lecture Notes in Computer Science). — ISBN 978-3-540-42287-7 . — DOI : 10.1007/3-540-48224-5_24 . .
Amit Chakrabarti, Subhash Khot , Yaoyun Shi. Evasiveness of subgraph containment and related properties // SIAM Journal on Computing . — 2001. — Т. 31 , вып. 3 . — С. 866–875 . — DOI : 10.1137/S0097539700382005 . .
Ehud Friedgut, Jeff Kahn, Avi Wigderson . Computing Graph Properties by Randomized Subcube Partitions // Randomization and Approximation Techniques in Computer Science. — Springer-Verlag , 2002. — Т. 2483. — С. 953. — (Lecture Notes in Computer Science). — ISBN 978-3-540-44147-2 . — DOI : 10.1007/3-540-45726-7_9 . .
Hans Dietmar Gröger. On the randomized complexity of monotone graph properties // Acta Cybernetica. — 1992. — Т. 10 , вып. 3 . — С. 119–127 . .
Péter Hajnal. An Ω( n ^4/3 ) lower bound on the randomized complexity of graph properties // Combinatorica . — 1991. — Т. 11 , вып. 2 . — С. 131–143 . — DOI : 10.1007/BF01206357 . .
Jeff Kahn, Michael Saks, Dean Sturtevant. A topological approach to evasiveness // 24th Annual Symposium on Foundations of Computer Science (sfcs 1983). Symposium on Foundations of Computer Science . — Los Alamitos, CA, USA: IEEE Computer Society, 1983. — С. 31–33. — ISBN 0-8186-0508-1 . — DOI : 10.1109/SFCS.1983.4 . .
Valerie King. Lower bounds on the complexity of graph properties // Proc. 20th ACM Symposium on Theory of Computing . — Chicago, Illinois, United States, 1988. — С. 468–476. — ISBN 0-89791-264-0 . — DOI : 10.1145/62212.62258 . .
Kleitman DJ, Kwiatkowski DJ Further results on the Aanderaa-Rosenberg conjecture // Journal of Combinatorial Theory, Series B. — 1980. — Т. 28 . — С. 85–95 . — DOI : 10.1016/0095-8956(80)90057-X .
Dmitry Kozlov. Combinatorial Algebraic Topology. — Springer-Verlag, 2008. — ISBN 978-3-540-73051-4 .
Frank H. Lutz. Some results related to the evasiveness conjecture // Journal of Combinatorial Theory, Series B. — 2001. — Т. 81 , вып. 1 . — С. 110–124 . — DOI : 10.1006/jctb.2000.2000 .
Torsten Korneffel, Eberhard Triesch. An asymptotic bound for the complexity of monotone graph properties // Combinatorica. — Springer-Verlag, 2010. — Т. 30 , вып. 6 . — С. 735–743 . — ISSN 0209-9683 . — DOI : 10.1007/s00493-010-2485-3 .
Frédéric Magniez, Miklos Santha, Mario Szegedy. Quantum algorithms for the triangle problem // Proceedings of the sixteenth annual ACM-SIAM symposium on Discrete algorithms . — Vancouver, British Columbia: Society for Industrial and Applied Mathematics , 2005. — С. 1109–1117. .
Ryan O'Donnell, Michael Saks, Oded Schramm, Rocco A. Servedio. Every decision tree has an influential variable // Proc 46th IEEE Symposium on Foundations of Computer Science . — 2005. — С. 31–39. — ISBN 0-7695-2468-0 . — DOI : 10.1109/SFCS.2005.34 .
Ronald L. Rivest , Jean Vuillemin. A generalization and proof of the Aanderaa-Rosenberg conjecture // Proc. 7th ACM Symposium on Theory of Computing . — Albuquerque, New Mexico, United States, 1975. — С. 6–11. — DOI : 10.1145/800116.803747 . .
Arnold L. Rosenberg. On the time required to recognize properties of graphs: a problem // SIGACT News. — 1973. — Т. 5 , вып. 4 . — С. 15–16 . — DOI : 10.1145/1008299.1008302 . .
Robert Scheidweiler, Eberhard Triesch. A Lower Bound for the Complexity of Monotone Graph Properties // SIAM Journal on Discrete Mathematics. — 2013. — Т. 27 , № 1 . — С. 257–265 . — DOI : 10.1137/120888703 .
Eberhard Triesch. On the recognition complexity of some graph properties // Combinatorica . — 1996. — Т. 16 , вып. 2 . — С. 259–268 . — DOI : 10.1007/BF01844851 . .
Andrew Chi-Chih Yao. Monotone bipartite graph properties are evasive // SIAM Journal on Computing . — 1988. — Т. 17 , вып. 3 . — С. 517–520 . — DOI : 10.1137/0217031 . .
Andrew Chi-Chih Yao. Lower bounds to randomized algorithms for graph properties // Journal of Computer and System Sciences . — 1991. — Т. 42 , вып. 3 . — С. 267–287 . — DOI : 10.1016/0022-0000(91)90003-N . .

Литература для дальнейшего чтения

Béla Bollobás. Chapter VIII. Complexity and packing // Extremal Graph Theory. — New York: Dover Publications , 2004. — С. 401–437. — ISBN 978-0-486-43596-1 .
László Lovász & Young, Neal E., "Lecture Notes on Evasiveness of Graph Properties", arΧiv : cs/0205031v1

Catherine E Chronaki. A survey of Evasiveness: Lower Bounds on the Decision-Tree Complexity of Boolean Functions. — 1990.
Michael Saks. Decision Trees: Problems and Results, Old and New (неопр.) .

[_eeab9d4acf9b2f11-1] ¹ ² Rivest, Vuillemin, 1975 .

[_56fb88d6ab458b5e-2] Rosenberg, 1973 .

[3] This definition of runoff is different from the usual definition of runoff. In this definition, it is assumed that all arcs of the graph enter one vertex (sink), and in the usual definition, it is only assumed that there are no outgoing arcs from the drain (see “ Types of graph vertices ”).

[_6ee1d651b2b024c2-4] ¹ ² Best, van Emde Boas, Lenstra, 1974 .

[_955709b347c2a0f6-5] Triesch, 1996 .

[_77e91d39c2da87a2-6] Kleitman, Kwiatkowski, 1980 .

[_68ce642735fbc174-7] ¹ ² Kahn, Saks, Sturtevant, 1983 .

[_9bce84b020f4d4a6-8] Korneffel, Triesch, 2010 .

[_f7064c1216040ba5-9] Scheidweiler, Triesch, 2013 .

[_104e2b1e0f47b467-10] Lutz, 2001 .

[_6c4da920a161670f-11] Kozlov, 2008 , с. 226-228.

[_2e5ee23c301ac982-12] Yao, 1988 .

[_b4f3800d194e965c-13] Chakrabarti, Khot, Shi, 2001 .

[_14d6517664ef5e0c-14] Yao, 1991 .

[_31e34eb7c0652b58-15] King, 1988 .

[_395a5b16c60ac27b-16] Hajnal, 1991 .

[_2bf4d3f4b6ae5ce0-17] Chakrabarti, Khot, 2001 .

[_d79175954c70ddaf-18] Friedgut, Kahn, Wigderson, 2002 .

[_dc7214fcb78ade96-19] O'Donnell, Saks, Schramm, Servedio, 2005 .

[_08e29aabe168d976-20] Gröger, 1992 .

[21] Результат не опубликован, но упомянут в статье Magniez, Santha & Szegedy (2005 )

[_eab525b884ef4ea1-22] Ambainis, Iwama, Nakanishi, Nishimura и др., 2008 .

[_2176f7de61361b1b-23] Beals, Buhrman, Cleve, Mosca, de Wolf, 2001 .