* (102) Sergeyev, Y.D., Kvasov, D.E.: Lipschitz global optimization.  In: J.J. Cochran, L.A. Cox, P. Keskinocak, J.P. Kharoufeh, J.C. Smith (eds.) Wiley Encyclopedia of Operations Research and Management Science (in 8 volumes), vol. 4, pp. 2812–2828. John Wiley & Sons, New York (2011)
  * (103) Sergeyev, Y.D., Kvasov, D.E., Mukhametzhanov, M.S.: A generator of multiextremal test classes with known solutions for black-box constrained global optimization.  IEEE Transactions on Evolutionary Computation pp. 1–1 (2021).  DOI 10.1109/TEVC.2021.3139263
  * (104) amir seyyedabbasi: Sand cat swarm optimization (2022).  URL https://www.mathworks.com/matlabcentral/fileexchange/110185-sand-cat-swarm-optimization.  MATLAB Central File Exchange. Retrieved May 9, 2022.
  * (105) Seyyedabbasi, A., Kiani, F.: Sand Cat swarm optimization: a nature-inspired algorithm to solve global optimization problems.  Engineering with Computers (2022).  DOI 10.1007/s00366-022-01604-x.  URL https://doi.org/10.1007/s00366-022-01604-x
  * (106) Shi, H.J.M., Xuan, M.Q., Oztoprak, F., Nocedal, J.: On the numerical performance of derivative-free optimization methods based on finite-difference approximations (2021).  DOI 10.48550/ARXIV.2102.09762.  URL https://arxiv.org/abs/2102.09762
  * (107) Shubert, B.O.: A sequential method seeking the global maximum of a function.  SIAM Journal on Numerical Analysis 9, 379–388 (1972).  DOI 10.1137/0709036
  * (108) Simon, D.: Biogeography-based optimization.  IEEE Transactions on Evolutionary Computation 12(6), 702–713 (2008).  DOI 10.1109/TEVC.2008.919004
  * (109) Storn, R., Price, K.: Differential Evolution – A Simple and Efficient Heuristic for global Optimization over Continuous Spaces.  Journal of Global Optimization 11(4), 341–359 (1997).  DOI 10.1023/A:1008202821328.  URL https://doi.org/10.1023/A:1008202821328
  * (110) Stripinis, L., Paulavičius, R.: DIRECTGO: A new DIRECT-type MATLAB toolbox for derivative-free global optimization (2022).  URL https://github.com/blockchain-group/DIRECTGO
  * (111) Stripinis, L., Paulavičius, R.: An empirical study of various candidate selection and partitioning techniques in the direct framework.  Journal of Global Optimization (2022).  DOI 10.1007/s10898-022-01185-5.  URL https://doi.org/10.1007/s10898-022-01185-5
  * (112) Stripinis, L., Paulavičius, R., Žilinskas, J.: Improved scheme for selection of potentially optimal hyper-rectangles in DIRECT.  Optimization Letters 12(7), 1699–1712 (2018).  DOI 10.1007/s11590-017-1228-4
  * (113) Stripinis, L., Paulavičius, R., Žilinskas, J.: Penalty functions and two-step selection procedure based DIRECT-type algorithm for constrained global optimization.  Structural and Multidisciplinary Optimization 59(6), 2155–2175 (2019).  DOI 10.1007/s00158-018-2181-2
  * (114) Stripinis, L., Paulavičius, R.: Directgo: A new direct-type matlab toolbox for derivative-free global optimization.  ACM Transactions on Mathematical Software (2022).  DOI 10.1145/3559755.  URL https://doi.org/10.1145/3559755
  * (115) Stripinis, L., Paulavičius, R.: DIRECTGOLib - DIRECT Global Optimization test problems Library (2022).  DOI 10.5281/zenodo.6617799.  URL https://doi.org/10.5281/zenodo.6617799
  * (116) Surjanovic, S., Bingham, D.: Virtual library of simulation experiments: Test functions and datasets.  http://www.sfu.ca/~ssurjano/index.html (2013).  Online; accessed: 2017-03-22
  * (117) Tsafarakis, S., Zervoudakis, K., Andronikidis, A., Altsitsiadis, E.: Fuzzy self-tuning differential evolution for optimal product line design.  European Journal of Operational Research 287(3), 1161–1169 (2020).  DOI https://doi.org/10.1016/j.ejor.2020.05.018.  URL https://www.sciencedirect.com/science/article/pii/S037722172030446X
  * (118) Ugray, Z., Lasdon, L., Plummer, J., Glover, F., Kelly, J., Martí, R.: Scatter Search and Local NLP Solvers: A Multistart Framework for Global Optimization.  INFORMS Journal on Computing 19(3), 328–340 (2007).  DOI 10.1287/ijoc.1060.0175.  URL https://doi.org/10.1287/ijoc.1060.0175
  * (119) Žilinskas, A., Zhigljavsky, A.: Stochastic global optimization: A review on the occasion of 25 years of informatica.  Informatica 27(2), 229–256 (2016).  DOI 10.15388/Informatica.2016.83
  * (120) Xi, M., Sun, W., Chen, J.: Survey of derivative-free optimization.  Numerical Algebra, Control & Optimization 10(4), 537–555 (2020)
  * (121) Yang, X.: The standard bat algorithm (ba) (2022).  URL https://www.mathworks.com/matlabcentral/fileexchange/74768-the-standard-bat-algorithm-ba.  MATLAB Central File Exchange. Retrieved February 18, 2022.
  * (122) Yang, X.: The standard cuckoo search (cs) (2022).  URL https://www.mathworks.com/matlabcentral/fileexchange/74767-the-standard-cuckoo-search-cs.  MATLAB Central File Exchange. Retrieved February 18, 2022.
  * (123) Yang, X.S.: Firefly algorithms for multimodal optimization.  In: O. Watanabe, T. Zeugmann (eds.) Stochastic Algorithms: Foundations and Applications, pp. 169–178. Springer Berlin Heidelberg, Berlin, Heidelberg (2009)
  * (124) Yang, X.S.: A New Metaheuristic Bat-Inspired Algorithm, pp. 65–74.  Springer Berlin Heidelberg, Berlin, Heidelberg (2010).  DOI 10.1007/978-3-642-12538-6˙6.  URL https://doi.org/10.1007/978-3-642-12538-6_6
  * (125) Yang, X.S., Deb, S.: Cuckoo search via lévy flights.  In: 2009 World Congress on Nature Biologically Inspired Computing (NaBIC), pp. 210–214 (2009).  DOI 10.1109/NABIC.2009.5393690
  * (126) Yarpiz: Shuffled frog leaping algorithm (sfla) (2022).  URL https://www.mathworks.com/matlabcentral/fileexchange/52861-shuffled-frog-leaping-algorithm-sfla
  * (127) Zavala, G.R., Nebro, A.J., Luna, F., Coello Coello, C.A.: A survey of multi-objective metaheuristics applied to structural optimization.  Structural and Multidisciplinary Optimization 49(4), 537–558 (2014).  DOI 10.1007/s00158-013-0996-4.  URL https://doi.org/10.1007/s00158-013-0996-4
  * (128) yiying zhang: Cclnna for global optimization (2022).  URL https://www.mathworks.com/matlabcentral/fileexchange/100601-cclnna-for-global-optimization.  MATLAB Central File Exchange. Retrieved February 18, 2022.
  * (129) Zhigljavsky, A., Žilinskas, A.: Stochastic Global Optimization.  Springer, New York (2008)

##  7 Appendix - DIRECTGOLib v1.2 library

Table 12: Key characteristics of box-constrained global optimization problems
(with varying $n$) from DIRECTGOLib v1.2 DIRECTGOLib2022 .

# | Name | Source | $D$ | $\tilde{D}$ | Type | No. of minima |  $f^{*}$
---|---|---|---|---|---|---|---
$1$ | Ackleyα | Hedar2005 ; Derek2013  | $[-15,30]^{n}$ |  $[-18,47]^{n}$ | non-convex | multi-modal |  $0.0000$
$2$ | AlpineN1αβ | Gavana2021  | $[-10,10]^{n}$ |  $[-10,7.5]^{n}$ | non-convex | multi-modal |  $0.0000$
$3$ | Alpineα | Gavana2021  | $[0,10]^{n}$ |  $[\sqrt[i]{2},8+\sqrt[i]{2}]^{i}$ | non-convex | multi-modal |  $-2.8081^{n}$
$4$ | Brownβ | Jamil2013  | $[-1,4]^{n}$ |  $-$ | convex | uni-modal |  $0.0000$
$5$ | ChungRβ | Jamil2013  | $[-100,350]^{n}$ |  $-$ | convex | uni-modal |  $0.0000$
$6$ | Csendesα | Gavana2021  | $[-10,10]^{n}$ |  $[-10,25]^{n}$ | convex | multi-modal |  $0.0000$
$7$ | Cubicβ | Derek2013  | $[-4,3]^{n}$ |  $-$ | convex | uni-modal |  $0.0000$
$8$ | Deb01α | Gavana2021  | $[-1,1]^{n}$ |  $[-0.55,1.45]^{n}$ | non-convex | multi-modal |  $-1.0000$
$9$ | Deb02α | Gavana2021  | $[0,1]^{n}$ |  $[0.225,1.225]^{n}$ | non-convex | multi-modal |  $-1.0000$
$10$ | Dixon_and_Price | Hedar2005 ; Derek2013  | $[-10,10]^{n}$ |  $-$ | convex | multi-modal |  $0.0000$
$11$ | Dejongβ | Derek2013  | $[-3,7]^{n}$ |  $-$ | convex | uni-modal |  $0.0000$
$12$ | Exponentialβ | Jamil2013  | $[-1,4]^{n}$ |  $-$ | non-convex | multi-modal |  $-1.0000$
$13$ | Exponential2β | Derek2013  | $[0,7]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$14$ | Exponential3β | Derek2013  | $[-30,20]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$15$ | Griewankα | Hedar2005 ; Derek2013  | $[-600,600]^{i}$ |  $[-\sqrt{600i},600\sqrt{i}^{-1}]^{i}$ | non-convex | multi-modal |  $0.0000$
$16$ | Layeb01αβ | Layeb2022  | $[-100,100]^{n}$ |  $[-100,90]^{n}$ | convex | uni-modal |  $0.0000$
$17$ | Layeb02β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | convex | uni-modal |  $0.0000$
$18$ | Layeb03αβ | Layeb2022  | $[-10,10]^{n}$ |  $[-10,12]^{n}$ | non-convex | multi-modal |  $-n+1$
$19$ | Layeb04β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $(ln(0.001)-1)$$(n-1)$
$20$ | Layeb05β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $(ln(0.001))$ $(n-1)$
$21$ | Layeb06β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$22$ | Layeb07αβ | Layeb2022  | $[-10,10]^{n}$ |  $[-10,12]^{n}$ | non-convex | multi-modal |  $0.0000$
$23$ | Layeb08β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $log(0.001)(n-1)$
$24$ | Layeb09β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$25$ | Layeb10β | Layeb2022  | $[-100,100]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$26$ | Layeb11β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $n-1$
$27$ | Layeb12β | Layeb2022  | $[-5,5]^{n}$ |  $-$ | non-convex | multi-modal |  $-(e+1)(n-1)$
$28$ | Layeb13β | Layeb2022  | $[-5,5]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$29$ | Layeb14β | Layeb2022  | $[-100,100]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$30$ | Layeb15β | Layeb2022  | $[-100,100]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$31$ | Layeb16β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$32$ | Layeb17β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$33$ | Layeb18β | Layeb2022  | $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal |  $ln(0.001)(n-1)$
$34$ | Levy | Hedar2005 ; Derek2013  | $[-5,5]^{n}$ |  $[-10,10]^{n}$ | non-convex | multi-modal |  $0.0000$
$35$ | Michalewicz | Hedar2005 ; Derek2013  | $[0,\pi]^{n}$ |  $-$ | non-convex | multi-modal |  $\chi$
$36$ | Pinterα | Gavana2021  | $[-10,10]^{n}$ |  $[-5.5,14.5]^{n}$ | non-convex | multi-modal |  $0.0000$
$37$ | Qing | Gavana2021  | $[-500,500]^{n}$ |  $-$ | non-convex | multi-modal |  $0.0000$
$38$ | Quadraticβ | Derek2013  | $[-2,3]^{n}$ |  $-$ | convex | uni-modal |  $0.0000$
$39$ | Rastriginα | Hedar2005 ; Derek2013  | $[-5.12,5.12]^{n}$ |  $[-5\sqrt[i]{2},7+\sqrt[i]{2}]^{i}$ | non-convex | multi-modal |  $0.0000$
$40$ | Rosenbrockα | Hedar2005 ; Dixon1978  | $[-5,10]^{n}$ |  $[-5\sqrt{i}^{-1},10\sqrt{i}]^{i}$ | non-convex | uni-modal |  $0.0000$
$41$ | Rotated_H_Ellipα | Derek2013  | $[-65.536,65.536]^{n}$ |  $[-35,95]^{n}$ | convex | uni-modal |  $0.0000$
$42$ | Schwefelα | Hedar2005 ; Derek2013  | $[-500,500]^{n}$ |  $[-500+100\sqrt{i}^{-1},$ $500-40\sqrt{i}^{-1}]^{i}$ | non-convex | multi-modal |  $0.0000$
$43$ | SineEnvelopeβ | Gavana2021  | $[-100,100]^{n}$ |  $-$ | non-convex | multi-modal |  $-2.6535(n-1)$
$44$ | Sinenvsinαβ | Mishra2006  | $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal |  $0.0000$
$45$ | Sphereα | Hedar2005 ; Derek2013  | $[-5.12,5.12]^{n}$ |  $[-2.75,7.25]^{n}$ | convex | uni-modal |  $0.0000$
$46$ | Styblinski_Tang | Clerc1999  | $[-5,5]^{n}$ |  $[-5,5+3^{1/i}]^{n}$ | non-convex | multi-modal |  $-39.1661n$
$47$ | Sum_Squaresα | Clerc1999  | $[-10,10]^{n}$ |  $[-5.5,14.5]^{n}$ | convex | uni-modal |  $0.0000$
$48$ | Sum_Of_Powersα | Derek2013  | $[-1,1]^{n}$ |  $[-0.55,1.45]^{n}$ | convex | uni-modal |  $0.0000$
$49$ | Trid | Hedar2005 ; Derek2013  | $[-100,100]^{n}$ |  $-$ | convex | multi-modal |  $-\frac{1}{6}n^{3}-\frac{1}{2}n^{2}+\frac{2}{3}n$
$50$ | Trigonometricαβ | Hedar2005 ; Derek2013  | $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal |  $0.0000$
$51$ | Vincent | Clerc1999  | $[0.25,10]^{n}$ |  $-$ | non-convex | multi-modal |  $-n$
$52$ | WWavyαβ | Jamil2013  | $[-\pi,\pi]^{n}$ |  $[-\pi,3\pi]^{n}$ | non-convex | multi-modal |  $0.0000$
$53$ | XinSheYajngN1β | Jamil2013  | $[-11,29]^{n}$ |  $[-11,29]^{n}$ | non-convex | multi-modal |  $-1.0000$
$54$ | XinSheYajngN2αβ | Jamil2013  | $[-\pi,\pi]^{n}$ |  $[-\pi,3\pi]^{n}$ | non-convex | multi-modal |  $0.0000$
$55$ | Zakharovα | Hedar2005 ; Derek2013  | $[-5,10]^{n}$ |  $[-1.625,13.375]^{n}$ | convex | multi-modal |  $0.0000$
$i$ – indexes used for variable bounds ($1,...,n$)
$\chi$ – solution depend on problem dimension
$\alpha$ – domain $D$ was perturbed
$\beta$ – New test problem in DIRECTGOLib v1.2

Table 13: Key characteristics of box-constrained global optimization problems
(with fixed $n$) from DIRECTGOLib v1.2 DIRECTGOLib2022 .

# | Name | Source | $n$ | $D$ | $\tilde{D}$ | Type | No. of minima | $f^{*}$
---|---|---|---|---|---|---|---|---
$1$ | AckleyN2αβ | Jamil2013  | $2$ |  $[-15,30]^{n}$ |  $[-18,47]^{n}$ | uni-modal | convex | $-200$
$2$ | AckleyN3αβ | Jamil2013  | $2$ |  $[-15,30]^{n}$ |  $[-18,47]^{n}$ | uni-modal | convex | $-186.4112$
$3$ | AckleyN4αβ | Jamil2013  | $2$ |  $[-15,30]^{n}$ |  $[-18,47]^{n}$ | non-convex | multi-modal | $-4.5901$
$4$ | Adjimanβ | Jamil2013  | $2$ |  $[-1,2]^{n}$ |  $-$ | non-convex | multi-modal | $-2.0218$
$5$ | BartelsConnαβ | Jamil2013  | $2$ |  $[-500,500]^{n}$ |  $[-300,700]^{n}$ | non-convex | multi-modal | $1.0000$
$6$ | Beale | Hedar2005 ; Derek2013  | $2$ |  $[-4.5,4.5]^{n}$ |  $-$ | non-convex | multi-modal | $0.0000$
$7$ | BiggsEXP2β | Jamil2013  | $2$ |  $[0,20]^{n}$ |  $-$ | non-convex | multi-modal | $0.000$
$8$ | BiggsEXP3β | Jamil2013  | $3$ |  $[0,20]^{n}$ |  $-$ | non-convex | multi-modal | $0.000$
$9$ | BiggsEXP4β | Jamil2013  | $4$ |  $[0,20]^{n}$ |  $-$ | non-convex | multi-modal | $0.000$
$10$ | BiggsEXP5β | Jamil2013  | $5$ |  $[0,20]^{n}$ |  $-$ | non-convex | multi-modal | $0.000$
$11$ | BiggsEXP6β | Jamil2013  | $6$ |  $[0,20]^{n}$ |  $-$ | non-convex | multi-modal | $0.000$
$12$ | Birdβ | Jamil2013  | $2$ |  $[-2\pi,2\pi]^{n}$ |  $-$ | non-convex | multi-modal | $-106.7645$
$13$ | Bohachevsky1α | Hedar2005 ; Derek2013  | $2$ |  $[-100,100]^{n}$ |  $[-55,145]^{n}$ | convex | uni-modal | $0.0000$
$14$ | Bohachevsky2α | Hedar2005 ; Derek2013  | $2$ |  $[-100,100]^{n}$ |  $[-55,145]^{n}$ | non-convex | multi-modal | $0.0000$
$15$ | Bohachevsky3α | Hedar2005 ; Derek2013  | $2$ |  $[-100,100]^{n}$ |  $[-55,145]^{n}$ | non-convex | multi-modal | $0.0000$
$16$ | Booth | Hedar2005 ; Derek2013  | $2$ |  $[-10,10]^{n}$ |  $-$ | convex | uni-modal | $0.0000$
$17$ | Bradβ | Jamil2013  | $3$ |  $[-0.25,0.25]\times[0.01,2.5]^{2}$ |  $-$ | non-convex | multi-modal | $6.9352$
$18$ | Branin | Hedar2005 ; Dixon1978  | $2$ |  $[-5,10]\times[10,15]$ |  $-$ | non-convex | multi-modal | $0.3978$
$19$ | Bukin4β | Jamil2013  | $2$ |  $[-15,-5]\times[-3,3]$ |  $-$ | convex | multi-modal | $0.0000$
$20$ | Bukin6 | Derek2013  | $2$ |  $[-15,5]\times[-3,3]$ |  $-$ | convex | multi-modal | $0.0000$
$21$ | CarromTableβ | Gavana2021  | $2$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $-24.1568$
$22$ | ChenBirdβ | Jamil2013  | $2$ |  $[-500,500]^{n}$ |  $-$ | non-convex | multi-modal | $-2000.0000$
$23$ | ChenVβ | Jamil2013  | $2$ |  $[-500,500]^{n}$ |  $-$ | non-convex | multi-modal | $-2000.0009$
$24$ | Chichinadzeβ | Jamil2013  | $2$ |  $[-30,30]^{n}$ |  $-$ | non-convex | multi-modal | $-42.9443$
$25$ | Colaβ | Jamil2013  | $17$ |  $[-4,4]^{n}$ |  $-$ | non-convex | multi-modal | $12.0150$
$26$ | Colville | Hedar2005 ; Derek2013  | $4$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $0.0000$
$27$ | Cross_functionβ | Gavana2021  | $2$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $0.00004$
$28$ | Cross_in_Tray | Derek2013  | $2$ |  $[0,10]^{n}$ |  $-$ | non-convex | multi-modal | $-2.0626$
$29$ | CrownedCrossβ | Gavana2021  | $2$ |  $[-10,15]^{n}$ |  $-$ | non-convex | multi-modal | $0.0001$
$30$ | Crosslegtable | Gavana2021  | $2$ |  $[-10,15]^{n}$ |  $-$ | non-convex | multi-modal | $-1.000$
$31$ | Cubeβ | Gavana2021  | $2$ |  $[-10,10]^{n}$ |  $-$ | convex | multi-modal | $0.000$
$32$ | Damavandi | Gavana2021  | $2$ |  $[0,14]^{n}$ |  $-$ | non-convex | multi-modal | $0.0000$
$33$ | Dejong5β | Derek2013  | $2$ |  $[-65.536,65.536]^{n}$ |  $-$ | non-convex | multi-modal | $0.9980$
$34$ | Dolanβ | Jamil2013  | $5$ |  $[-100,100]^{n}$ |  $-$ | non-convex | multi-modal | $-529.8714$
$35$ | Drop_waveα | Derek2013  | $2$ |  $[-5.12,5.12]^{n}$ |  $[-4,6]^{n}$ | non-convex | multi-modal | $-1.0000$
$36$ | Easomα | Hedar2005 ; Derek2013  | $2$ |  $[-100,100]^{n}$ |  $[-100(i+1)^{-1},100i]^{i}$ | non-convex | multi-modal | $-1.0000$
$37$ | Eggholder | Derek2013  | $2$ |  $[-512,512]^{n}$ |  $-$ | non-convex | multi-modal | $-959.6406$
$38$ | Giuntaβ | Gavana2021  | $2$ |  $[-1,1]^{n}$ |  $-$ | non-convex | multi-modal | $0.0644$
$39$ | Goldstein_and_Priceα | Hedar2005 ; Dixon1978  | $2$ |  $[-2,2]^{n}$ |  $[-1.1,2.9]^{n}$ | non-convex | multi-modal | $3.0000$
$40$ | Hartman3 | Hedar2005 ; Derek2013  | $3$ |  $[0,1]^{n}$ |  $-$ | non-convex | multi-modal | $-3.8627$
$41$ | Hartman4β | Hedar2005 ; Derek2013  | $4$ |  $[0,1]^{n}$ |  $-$ | non-convex | multi-modal | $-3.1344$
$42$ | Hartman6 | Hedar2005 ; Derek2013  | $6$ |  $[0,1]^{n}$ |  $-$ | non-convex | multi-modal | $-3.3223$
$43$ | HelicalValleyβ | Gavana2021  | $3$ |  $[-10,20]^{n}$ |  $-$ | convex | multi-modal | $0.0000$
$44$ | HimmelBlauβ | Gavana2021  | $2$ |  $[-5,5]^{n}$ |  $-$ | convex | multi-modal | $0.0000$
$45$ | Holder_Table | Derek2013  | $2$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $-19.2085$
$46$ | Hump | Hedar2005 ; Derek2013  | $2$ |  $[-5,5]^{n}$ |  $-$ | non-convex | multi-modal | $-1.0316$
$47$ | Langermann | Derek2013  | $2$ |  $[0,10]^{n}$ |  $-$ | non-convex | multi-modal | $-4.1558$
$48$ | Leonβ | Gavana2021  | $2$ |  $[-1.2,1.2]^{n}$ |  $-$ | convex | multi-modal | $0.0000$
$49$ | Levi13β | Gavana2021  | $2$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $0.0000$
$50$ | Matyasα | Hedar2005 ; Derek2013  | $2$ |  $[-10,10]^{n}$ |  $[-5.5,14.5]^{n}$ | convex | uni-modal | $0.0000$
$51$ | McCormick | Derek2013  | $2$ |  $[-1.5,4]\times[-3,4]$ |  $-$ | convex | multi-modal | $-1.9132$
$52$ | ModSchaffer1αβ | Mishra2006  | $2$ |  $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal | $0.0000$
$53$ | ModSchaffer2αβ | Mishra2006  | $2$ |  $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal | $0.0000$
$54$ | ModSchaffer3αβ | Mishra2006  | $2$ |  $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal | $0.0015$
$55$ | ModSchaffer4αβ | Mishra2006  | $2$ |  $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal | $0.2925$
$56$ | PenHolderβ | Hedar2005 ; Derek2013  | $2$ |  $[-11,11]^{n}$ |  $-$ | non-convex | multi-modal | $-0.9635$
$57$ | Permdb4 | Hedar2005 ; Derek2013  | $4$ |  $[-i,i]^{i}$ |  $-$ | non-convex | multi-modal | $0.0000$
$58$ | Powell | Hedar2005 ; Derek2013  | $4$ |  $[-4,5]^{n}$ |  $-$ | convex | multi-modal | $0.0000$
$59$ | Power_Sumα | Hedar2005 ; Derek2013  | $4$ |  $[0,4]^{n}$ |  $[1,4+\sqrt[i]{2}]^{i}$ | convex | multi-modal | $0.0000$
$60$ | Shekel5 | Hedar2005 ; Derek2013  | $4$ |  $[0,10]^{n}$ |  $-$ | non-convex | multi-modal | $-10.1531$
$61$ | Shekel7 | Hedar2005 ; Derek2013  | $4$ |  $[0,10]^{n}$ |  $-$ | non-convex | multi-modal | $-10.4029$
$62$ | Shekel10 | Hedar2005 ; Derek2013  | $4$ |  $[0,10]^{n}$ |  $-$ | non-convex | multi-modal | $-10.5364$
$63$ | Shubert | Hedar2005 ; Derek2013  | $2$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $-186.7309$
$64$ | TestTubeHolderβ | Gavana2021  | $2$ |  $[-10,10]^{n}$ |  $-$ | non-convex | multi-modal | $-10.8722$
$65$ | Trefethen | Gavana2021  | $2$ |  $[-2,2]^{n}$ |  $-$ | non-convex | multi-modal | $-3.3068$
$66$ | Woodαβ | Mishra2006  | $4$ |  $[-100,100]^{n}$ |  $[-100,150]^{n}$ | non-convex | multi-modal | $0.0000$
$67$ | Zettlβ | Gavana2021  | $2$ |  $[-5,5]^{n}$ |  $-$ | convex | multi-modal | $-0.0037$
$i$ – indexes used for variable bounds ($1,...,n$) |
$\alpha$ – domain $D$ was perturbed |
$\beta$ – New test problem in DIRECTGOLib v1.2 |


# Slicing all Edges of an $n$-cube Requires $n^{2/3}$ Hyperplanes

Ohad Klein School of Computer Science and Engineering, Hebrew University of
Jerusalem<EMAIL_ADDRESS>
This research was supported in part by a grant from the Israel Science
Foundation (ISF Grant No. 1774/20), and by a grant from the US-Israel
Binational Science Foundation and the US National Science Foundation (BSF-NSF
Grant No. 2020643).

###### Abstract

Consider the $n$-cube graph with vertices $\left\\{-1,1\right\\}^{n}$ and
edges connecting vertices with hamming distance $1$. How many hyperplanes in
$\mathbb{R}^{n}$ are needed in order to dissect all edges? We show that at
least $\widetilde{\Omega}(n^{2/3})$ are needed, which improves the previous
bound of $\Omega(n^{0.51})$ by Yehuda and Yehudayoff.

##  1 Introduction

Consider the hypercube graph $Q_{n}$ consisting of the vertices
$\left\\{-1,1\right\\}^{n}\subset\mathbb{R}^{n}$ with edges connecting
adjacent vertices $x,y$ satisfying $\sum_{i=1}^{n}|x_{i}-y_{i}|=2$. It was
asked how many hyperplanes in $\mathbb{R}^{n}$ are required in order to
dissect111A hyperplane dissects an edge if it intersects the edge, but does
not contain any of its endpoints. In such a case we also say that the edge
crosses the hyperplane. One may relax the notion to allow the hyperplane to
include at most one of the endpoints – our result will carry over and incur a
multiplicative constant degradation. all edges of $Q_{n}$ – call this quantity
$H(n)$. There are several natural configurations of hyperplanes involving $n$
hyperplanes, yielding $H(n)\leq n$. However, there is a configuration
involving only $5$ planes in $6$ dimensions that was found by Paterson [6],
implying that $H(n)\leq\lceil\frac{5n}{6}\rceil$. On the lower bound front,
each hyperplane can dissect at most $\lceil n/2\rceil\cdot\binom{n}{\lceil
n/2\rceil}$ edges [8, Chapter 7.E], out of $n\cdot 2^{n-1}$ – hence at least
$\Omega(\sqrt{n})$ hyperplanes are required. Even though the problem was posed
in the 70s [4, 2], only recently a better lower bound of $\Omega(n^{0.51})$
was given by Yehuda and Yehudayoff [9] (for the history of the problem and its
applications, see references therein). In this paper we prove the following.

######  Theorem 1.1.

$H(n)\geq\Omega(n^{2/3}/\log(n)^{4/3}).$

While it is likely that the inverse logarithmic factors can be improved, we
are unaware of polynomial improvements. Some tools, especially the anti-
concentration arguments are shared with [9], but the general approach seems to
be different.

###  1.1 Proof overview

The lower bound $H(n)\geq\Omega(\sqrt{n})$ proceeds by showing each hyperplane
dissects at most $O(1/\sqrt{n})$ of the available edges in $Q_{n}$.

#### Example of middle layers.

In fact, once we surpass $O(\sqrt{n})$ hyperplanes, the planes can dissect
almost all edges. To see this, partition all edges of the hypercube into $n+1$
layers, the $k$’th of which connects vertices of Hamming weight $k$ to those
with weight $k+1$. Each such layer is dissected by a hyperplane orthogonal to
the vector $(1,\ldots,1)$. Most edges in the hypercube are contained in the
$O(\sqrt{n})$ middle layers, thus a uniformly random edge is likely to cross
some hyperplane in a fixed set of $O(\sqrt{n})$ planes.

######  Question.

Is there a (natural) distribution over edges which is likely to _evade_ (i.e.
not cross) a set of $m$ hyperplanes?

In our example, the answer is positive – choose a uniformly random layer in
$Q_{n}$ (out of $n$), and draw a random edge $E$ within that layer. What about
a general configuration of planes?

#### Setting.

Assume $m$ hyperplanes are given, with the $\ell$’th hyperplane specified by

$H_{\ell}=\left\\{x\in\mathbb{R}^{n}\,\middle|\,\langle{v_{\ell}},{x}\rangle=t_{\ell}\right\\},$
(1)

with $v_{\ell}\in\mathbb{R}^{n}$ having $\left\|{v_{\ell}}\right\|_{2}=1$ and
$t_{\ell}\in\mathbb{R}$.

#### Middle layers revisited.

We present a different view for why in the example of the middle layers, the
random edge $E$ is likely to evade a small set of hyperplanes having
$v_{\ell}=\frac{1}{\sqrt{n}}(1,\ldots,1)$. When projecting the edge $E$ on
$v_{\ell}$, we produce an interval of length $2/\sqrt{n}$ that is located
anywhere on $(-\sqrt{n},\sqrt{n})\cdot v_{\ell}$ equally likely. Meanwhile
each layer $H_{\ell}$ projected on $v_{\ell}$ is a single point. Hence
$\Omega(n)$ hyperplanes with $v_{\ell}=\frac{1}{\sqrt{n}}(1,\ldots,1)$ are
required in order to dissect all edges.

#### The general case.

In general, projecting an edge on $v_{\ell}$ results in an interval of length
$\leq 2\left\|{v_{\ell}}\right\|_{\infty}$ parallel to $v_{\ell}$. Assuming
$\left\|{v_{\ell}}\right\|_{\infty}=\widetilde{O}(1/\sqrt{n})$ (which holds
for a uniformly random vector $v_{\ell}$ with norm $1$), we have that each
edge corresponds to an interval of length $\widetilde{O}(1/\sqrt{n})$ on
$v_{\ell}$, while $H_{\ell}$ is projected to a point. Hence, if we are able to
produce a random edge whose projection on any $v_{\ell}$ has a significant
variance – it will likely evade every $H_{\ell}$.

#### The distribution.

Keeping the assumption
$\left\|{v_{\ell}}\right\|_{\infty}=\widetilde{O}(1/\sqrt{n})$ for the $m$
hyperplanes, let

$P=\sum_{\ell=1}^{m}\alpha_{\ell}\sqrt{\frac{n}{m}}v_{\ell},$

with $\alpha_{\ell}\sim U([-1,1])$ independently. Note that each coordinate
$P_{i}$ has $\operatorname*{\mathbb{E}}[P_{i}]=0$ and
$\operatorname*{\mathrm{Var}}[P_{i}]=(n/3m)\sum_{\ell=1}^{m}v_{\ell
i}^{2}=\widetilde{O}(1)$. Hence we (informally) imagine $P$ as a vertex in
$\left\\{-1,1\right\\}^{n}$. Moreover, the standard deviation of the (norm of
the) projection of $P$ on $v_{\ell}$ is at least $\Omega(\sqrt{n/m})$.
Considering a uniformly random edge incident to $P$, the probability that the
projection of this edge on $v_{\ell}$ (which has length
$\widetilde{O}(1/\sqrt{n})$) crosses the projection of $H_{\ell}$ on
$v_{\ell}$ (which is a single point), is about
$(1/\sqrt{n})/\sqrt{n/m}=\sqrt{m}/n$. Since there are $m$ hyperplanes, and we
wish the edge to evade all of them, it is sufficient that $m\cdot\sqrt{m}/n\ll
1$, or in other words, $m\ll n^{2/3}$.

#### Getting rid of the assumption.

Although abandoning the assumption
$\left\|{v_{\ell}}\right\|_{\infty}=\widetilde{O}(1/\sqrt{n})$ introduces a
few technicalities in the proof, it does not severely affect the general
approach. We get $v_{\ell}$ decomposed into different groups of coordinates,
such that $v_{\ell}$ is roughly constant on each group. We call this process a
‘binary decomposition’. Then, we slightly alter the definition of $P$ and the
rest of the proof generalizes smoothly.

#### Organization.

In Sections 2.1-2.2 we define a distribution over edges. Sections 2.3-2.4
introduce linear forms and some of their anti-concentration properties.
Finally, Section 2.5 shows the distribution evades the hyperplanes. Appendix A
contains proofs of standard facts that are used in the paper.

##  2 Proof

###  2.1 A random bounded vector correlating with all $v_{\ell}$

The proof overview in Section 1.1 assumes that
$\left\|{v_{\ell}}\right\|_{\infty}$ is small. The following definition is
useful in order to deal with general vectors $v_{\ell}$.

######  Definition 2.1 (Vector Binary Decomposition).

Let $v\in\mathbb{R}^{n}$. For an integer $j$, let $K(j)$ be the set of
coordinates of $v$ whose absolute value is in the range $(2^{-j-1},2^{-j}]$,
that is

$K(j)=\left\\{k\in[n]\,\middle|\,2^{-j-1}<|v_{k}|\leq 2^{-j}\right\\}.$

Let $J$ be these $j$’s for which $K(j)$ is nonempty. The Binary decomposition
of $v$ is

$v=\sum_{j\in J}v^{(j)},$

where $v^{(j)}\in\mathbb{R}^{n}$ aggregates all coordinates $K(j)$, that is

$v^{(j)}_{k}=v_{k}\cdot\boldsymbol{1}\left\\{k\in K(j)\right\\}.$

######  Definition 2.2 (The Random Bias).

Let $v_{1},\ldots,v_{m}$ be vectors in $\mathbb{R}^{n}$ having
$\left\|{v_{\ell}}\right\|_{2}=1$ for all $\ell$. Let $v_{\ell}=\sum_{j\in
J_{\ell}}v_{\ell}^{(j)}$ be the Binary decomposition of $v_{\ell}$, according
to Definition 2.1. Define the random variable

$P\mathrel{\mathop{:}}=\frac{1}{10\sqrt{m\log(n)}}\sum_{\ell=1}^{m}\sum_{j\in
J_{\ell}}\alpha_{\ell j}2^{j}v_{\ell}^{(j)}$

with $\alpha_{\ell j}\sim U([-1,1])$ uniformly and independently distributed
in the interval $[-1,1]$.

We will use $P$ in order to produce a product distribution over
$\left\\{-1,1\right\\}^{n}$ which has mean $P$. For the sake of this
distribution not to be too biased, we note that with high probability
$\|{P}\|_{\infty}\leq 1/2$; the simple proof appears in Appendix A.

######  Lemma 2.3.

Let $P$ be distributed as in Definition 2.2, then

$\Pr[\|{P}\|_{\infty}>1/2]\leq 2/n,$

where the randomness is taken over the distribution of $\alpha_{\ell j}$’s.

###  2.2 Hyperplane-evasive edges

######  Definition 2.4.

Given a vector $p\in[-1,1]^{n}$, we define a probability distribution
$\mu_{p}$ on vectors $z\in\left\\{-1,1\right\\}^{n}$, by letting $z_{i}$ be
independent random variables with

$\Pr[z_{i}=1]=\frac{1+p_{i}}{2},\qquad\Pr[z_{i}=-1]=\frac{1-p_{i}}{2}.$

We now define a distribution on edges of $Q_{n}$ which are likely to evade
every $H_{\ell}$.

######  Definition 2.5.

Let $H_{i},v_{i},t_{i}$ be as in Section 1.1, and let $P$ be a random variable
which is distributed according to Definition 2.2, conditioned on that
$\|{P}\|_{\infty}\leq 1/2$.

Let $U$ be a random vertex of $Q_{n}$ drawn from $\mu_{P}$, and let $k\sim[n]$
be uniformly distributed. We define $(U,k)$ as the edge which is incident to
$U$ and is parallel to the $k$’th axis.

Our main technical result is the following proposition, which states that the
probability of the edge $(U,k)$ to cross any of the hyperplanes $H_{i}$ is
small.

######  Proposition 2.6.

Let $(U,k)$ be distributed as in Definition 2.5. Then for all $\ell$,

$\Pr[(U,k)\text{ crosses }H_{\ell}]\leq O\left(\sqrt{m}\log(n)^{2}/n\right).$
(2)

######  Corollary 2.7 (Restatement of Theorem 1.1).

$H(n)\geq\Omega(n^{2/3}/\log(n)^{4/3}).$

###### Proof.

Suppose the hyperplanes $H_{1},\ldots,H_{m}$ from (1) dissect all edges of
$Q_{n}$. Since $(U,k)$ is a distribution over edges of $Q_{n}$, we have
$\Pr[\exists i\colon(U,k)\text{ crosses }H_{i}]=1$. However, by union bound
and Proposition 2.6,

$\Pr[\exists i\colon(U,k)\text{ crosses
}H_{i}]\leq\sum_{i=1}^{m}\Pr[(U,k)\text{ crosses }H_{i}]\leq
O\left(m^{3/2}\log(n)^{2}/n\right).$

This yields $m\geq\Omega(n^{2/3}/\log(n)^{4/3})$. ∎

We prove Proposition 2.6 using anti-concentration techniques. In order to
phrase our result in a probabilistic setting, we use the following claim.

######  Claim 2.8.

In order for an edge $(u,k)$ to cross the hyperplane
$H=\left\\{x\in\mathbb{R}^{n}\,\middle|\,\langle{v},{x}\rangle=t\right\\}$ we
must have

$|\langle{v},{u}\rangle-t|<2|v_{k}|.$ (3)

###### Proof.

Let $u^{\prime}$ be the vertex connected to $u$ by $(u,k)$. That is,
$u^{\prime}$ is either $u+2e_{k}$ or $u-2e_{k}$. In order for the edge $(u,k)$
to cross
$\left\\{x\in\mathbb{R}^{n}\,\middle|\,\langle{v},{x}\rangle=t\right\\}$ we
must have that $\langle{v},{u}\rangle-t$ and
$\langle{v},{u^{\prime}}\rangle-t$ have different signs (and are nonzero).
Since $\langle{v},{u^{\prime}}\rangle=\langle{v},{u\pm
2e_{k}}\rangle=\langle{v},{u}\rangle\pm 2v_{k}$, the edge $(u,k)$ may cross
$H$ only if (3) holds. ∎

###  2.3 Linear forms

######  Definition 2.9 (Biased Linear Form).

Let $v,p\in\mathbb{R}^{n}$ have $\|{p}\|_{\infty}\leq 1$ and let
$x\sim\mu_{p}$. We define the associated biased linear form to be the random
variable

$X_{v,p}\mathrel{\mathop{:}}=\langle{v},{x}\rangle.$

We recall a standard tail inequality for linear forms.

######  Claim 2.10 (Chernoff-Hoeffding inequality [3]).

Let $p,v\in\mathbb{R}^{n}$ have $\|{p}\|_{\infty}\leq 1$. Then for any
$\sigma>0$,

$\Pr_{x\sim\mu_{p}}[|X_{v,p}-\langle{v},{p}\rangle|>\sigma\|{v}\|_{2}]\leq
2\exp(-\sigma^{2}/2).$ (4)

###  2.4 Anti-concentration of linear forms

######  Definition 2.11 (Lévy Concentration function).

Let $X$ be a random variable. It’s $\alpha$-concentration is defined as

$Q(\alpha,X)\mathrel{\mathop{:}}=\sup_{t\in\mathbb{R}}\Pr[|X-t|<\alpha].$

We need a basic property of concentration functions.

######  Claim 2.12.

Every random variable $X$ and integer $k\geq 1$ satisfies $Q(k\alpha,X)\leq
kQ(\alpha,X)$.

###### Proof.

Follows by (almost) covering an interval of length $2k\alpha$ using $k$
intervals of length $2\alpha$ (and taking a limit). ∎

Next, we need a simple Littlewood-Offord-type result regarding the anti-
concentration of a biased linear form $X$. For example, it follows from [5].
For completeness, we include a quick proof in Appendix A.

######  Lemma 2.13.

There is a universal constant $C\geq 1$, such that the following holds. Let
$X_{v,p}$ be a biased linear form with $\|{p}\|_{\infty}\leq 1/2$. Suppose
that $\alpha$ satisfies $\alpha\leq\min\\{|v_{1}|,\ldots,|v_{a}|\\}$, then

$Q(\alpha,X_{v,p})\leq C/\sqrt{a}.$

While Lemma 2.13 gives at most an $O(1/\sqrt{n})$ bound on $Q(\alpha,X_{v,p})$
we can sometimes exponentially improve this bound, as the following lemma
demonstrates.

######  Lemma 2.14.

Let $v,p\in\mathbb{R}^{n}$ have $\|{p}\|_{\infty}\leq 1/2$. Suppose $v$ has a
binary decomposition

$v=\sum_{j\in J}v^{(j)},$

with the corresponding partition of the nonzero coordinates as $\bigcup_{j\in
J}K(j)$. Let $\alpha>0$ have at least $2r\log(n)$ elements $j\in J$ with
$2^{-j-1}\geq\alpha$, where $r\geq 0$ is an integer.

  1. 1.

Let $C$ be the universal constant from Lemma 2.13. If $n\geq 10\exp(10C^{2})$,
then

$Q(\alpha,X_{v,p})\leq 2^{-r}.$ (5)

  2. 2.

For all $n$,

$Q(\alpha,X_{v,p})\leq O(2^{-r}).$ (6)

###### Proof.

The proof of (5) is by induction on $r$, where the $r=0$ case is trivial.

Let $L=\lceil 4C^{2}\rceil$ and $j_{1}<\ldots<j_{L}$ be the $L$ largest $j\in
J$ satisfying $2^{-j-1}\geq\alpha$. Denote

$\alpha^{\prime}\mathrel{\mathop{:}}=\sum_{j\geq j_{1}}\|{v^{(j)}}\|_{1}.$

######  Claim 2.15.

There are at least $2(r-1)\log(n)$ elements $j\in J$ with $2^{-j-1}\geq
2\alpha^{\prime}$.

To prove Claim 2.15, observe that $2\alpha^{\prime}\leq 2n\cdot 2^{-j_{1}}$,
hence there are at most $\log_{2}(2n)$ elements $j\in J$ with $j<j_{1}$ and
$2^{-j-1}<\alpha^{\prime}$. Including $j_{1},\ldots,j_{L}$, there are at most
$\log_{2}(2n)+L$ elements $j\in J$ with $2^{-j-1}\in[\alpha,\alpha^{\prime})$.
Since $n\geq 10\exp(10C^{2})$, we have $\log_{2}(2n)+L\leq 2\log(n)$, thus
establishing Claim 2.15.$\hfill\blacksquare$

Given a decomposition $v=u+w$ we have $X_{v,p}=X_{u,p}+X_{w,p}$. We set

$u\mathrel{\mathop{:}}=\sum_{j\in J\colon j<j_{1}}v^{(j)},\qquad
w\mathrel{\mathop{:}}=\sum_{j\in J\colon j\geq j_{1}}v^{(j)}.$

Since $u$ and $w$ are supported on different coordinates, we have that
$X_{u,p}$ and $X_{w,p}$ are independent random variables.

We use the induction hypothesis (5) with $2\alpha^{\prime}$ instead of
$\alpha$ and obtain

$Q(2\alpha^{\prime},X_{u,p})\leq 2^{1-r}.$

We immediately complete the inductive proof of (5) using the following claim.

######  Claim 2.16.

$Q(\alpha,X_{v,p})\leq\frac{1}{2}Q(2\alpha^{\prime},X_{u,p})$.

In order to prove Claim 2.16 we show the following for all $t\in\mathbb{R}$

$\Pr[|X_{v,p}-t|<\alpha]\leq\frac{1}{2}\Pr[|X_{u,p}-t|<2\alpha^{\prime}].$

Indeed, note that by definition of $\alpha^{\prime}$ we always have
$|X_{w,p}|\leq\alpha^{\prime}$. Hence, if $|X_{v,p}-t|<\alpha$ then
necessarily $|X_{u,p}-t|<\alpha^{\prime}+\alpha<2\alpha^{\prime}$. Conditioned
on any specific value of $X_{u,p}$, we also need that

$|X_{w,p}-(t-X_{u,p})|=|X_{v,p}-t|<\alpha.$ (7)

However, since $X_{w,p}$ is independent of $X_{u,p}$, the probability that (7)
holds is upper bounded by $Q(\alpha,X_{w,p})$. Therefore,
$Q(\alpha,X_{v,p})\leq Q(2\alpha^{\prime},X_{u,p})\cdot Q(\alpha,X_{w,p})$,
and Claim 2.16 follows from

$Q(\alpha,X_{w,p})\leq 1/2.$ (8)

To confirm (8) note that $w$ contains at least $L$ coordinates greater than
$\alpha$, which reside in the non-empty sets $K(j_{1}),\ldots,K(j_{L})$, hence
Lemma 2.13 implies $Q(\alpha,X_{w,p})\leq C/\sqrt{L}\leq 1/2$.
$\hfill\blacksquare$

The proof of (5) is complete. Finally, observe that (6) follows from (5) – by
plugging in a large enough constant in the right hand side of (6), it holds
even when $n<10\exp(10C^{2})$. ∎

###  2.5 Evasiveness of Definition 2.5

######  Lemma 2.17.

Let $\bar{v}_{1},\ldots,\bar{v}_{m}$ be vectors in $\mathbb{R}^{n}$ with
$\left\|{\bar{v}_{i}}\right\|_{2}=1$, and suppose that $P$ is distributed
according to Definition 2.2, conditioned on $\|{P}\|_{\infty}\leq 1/2$. If
$x\sim\mu_{P}$, then for $v=\bar{v}_{1}$ and $t\in\mathbb{R}$ we have

$\sum_{k=1}^{n}\Pr_{x\sim\mu_{P}}[|\langle{v},{x}\rangle-t|<2|v_{k}|]\leq
O(\sqrt{m}\log(n)^{2}).$ (9)

This lemma immediately implies our main technical result.

###### Proof of Proposition 2.6.

Since $k$ in Definition 2.5 is uniformly random (out of $n$ options), Lemma
2.17 implies (2) through Claim 2.8. ∎

###### Proof of Lemma 2.17.

Suppose $v=\bar{v}_{1}$ has the binary decomposition

$v=\sum_{j\in J}v^{(j)},$

with the corresponding partition of the nonzero coordinates as $\bigcup_{j\in
J}K(j)$. We show the following. If $i\in J$ has at least $2r\log(n)$ elements
in $J$ smaller than $i$, with $r\geq 0$ an integer, then

$\sum_{k\in K({i})}\Pr_{x\sim\mu_{P}}[|\langle{v},{x}\rangle-t|<2|v_{k}|]\leq
O\left(2^{-r}\sqrt{m}\log(n)+\frac{|K({i})|}{n}\right).$ (10)

Note that the probability is taken both with respect to $P$ and
$x\sim\mu_{P}$. Let us see that (10) implies (9):

$\displaystyle\sum_{k=1}^{n}\Pr_{x\sim\mu_{P}}[|\langle{v},{x}\rangle-t|<2|v_{k}|]$
$\displaystyle=\sum_{j\in J}\sum_{k\in
K({j})}\Pr_{x\sim\mu_{P}}[|\langle{v},{x}\rangle-t|<2|v_{k}|]$
$\displaystyle\leq O\left(\sum_{j\in
J}2^{-r(j)}\sqrt{m}\log(n)+\frac{|K({j})|}{n}\right)$ $\displaystyle\leq
O\left(\sqrt{m}\log(n)^{2}\right)+O(1),$

with $r(j)$ the maximal $r$ corresponding to $j$. Note that $\sum_{j\in
J}2^{-r(j)}=O(\log(n))$ as a sum of a geometric progression with each term
appearing $\approx 2\log(n)$ times. The estimate (9) follows.

Proving (10). We let $\sigma\mathrel{\mathop{:}}=2+2\sqrt{\log(n)}$ and define
the events

$E\mathrel{\mathop{:}}=E_{1}\cup
E_{2}\mathrel{\mathop{:}}=\left\\{|\langle{v-v^{(i)}},{x}\rangle-t|\geq
3\|{v^{(i)}}\|_{1}\right\\}\cup\left\\{|\langle{v-v^{(i)}},{x}\rangle+\langle{v^{(i)}},{P}\rangle-t|\geq\sigma\|{v^{(i)}}\|_{2}\right\\},$

that split the probability space into $E$ and $\neg{E}$. We prove later that

$\forall k\in
K(i)\colon\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,E\right]\leq
O\left(1/n\right).$ (11)

and

$\Pr[\neg{E}]\leq O\left(2^{-r}\sigma\sqrt{\frac{m\log(n)}{|K({i})|}}\right),$
(12)

This allows us to bound the terms on the left hand side of (10) as

$\displaystyle\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\right]$
$\displaystyle=\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,E\right]\Pr[E]+\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,\neg{E}\right]\Pr[\neg{E}]$
(13) $\displaystyle\leq
O(1/n)+\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,\neg{E}\right]\cdot
O\left(2^{-r}\sigma\sqrt{\frac{m\log(n)}{|K({i})|}}\right),$

for all $k\in K(i)$. Observe that conditioning on the value of $P$, the event
$E$ is independent of the $K(i)$ coordinates of $x$. Hence, under any fixing
of $P=p$,

$\Pr_{x\sim\mu_{p}}\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,\neg{E},P=p\right]\leq
Q(2|v_{k}|,X_{v^{(i)},p})\leq 2Q(|v_{k}|,X_{v^{(i)},p}),$ (14)

using Claim 2.12. Assuming $|v_{k}|$ is the $a$’th largest coordinate in
$v^{(i)}$, Lemma 2.13 implies that $Q(|v_{k}|,X_{v^{(i)},P})\leq
O(1/\sqrt{a})$ (recall that we conditioned on $\|{P}\|_{\infty}\leq 1/2$).
Together with (14) this yields

$\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,\neg{E}\right]=\operatorname*{\mathbb{E}}_{P}\left[\Pr_{x\sim\mu_{P}}\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,\neg{E},P\right]\right]\leq
O(1/\sqrt{a}).$

Computing the sum over all $k\in K(i)$ we refine (13) into

$\displaystyle\sum_{k\in
K(i)}\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\right]$
$\displaystyle\leq\sum_{a=1}^{|K(i)|}\left(O(1/n)+O(1/\sqrt{a})\cdot
O\left(2^{-r}\sigma\sqrt{\frac{m\log(n)}{|K({i})|}}\right)\right)$
$\displaystyle=O\left(\frac{|K(i)|}{n}+2^{-r}\sqrt{m}\log(n)\right),$

yielding (10). It remains to verify (11) and (12).

Proving (11). Recall $E$ is the union of the two events $E_{1}$ and $E_{2}$.
Under $E_{1}$ we actually have the stronger

$\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,E_{1}\right]=0.$ (15)

Indeed, if $E_{1}$ happens then

$\displaystyle\left|\langle{v},{x}\rangle-t\right|$
$\displaystyle=\left|\langle{v-v^{(i)}},{x}\rangle+\langle{v^{(i)}},{x}\rangle-t\right|$
$\displaystyle\geq\left|\langle{v-v^{(i)}},{x}\rangle-t\right|-\left|\langle{v^{(i)}},{x}\rangle\right|$
$\displaystyle\geq 3\|{v^{(i)}}\|_{1}-\|{v^{(i)}}\|_{1}$
$\displaystyle=2\|{v^{(i)}}\|_{1}\geq 2|v_{1k}|,$

giving (15). We now prove (11) with $E_{2}$ instead of $E$. If $E_{2}$
happens, then $|\langle{v},{x}\rangle-t|<2|v_{k}|$ means

$\displaystyle\left|\langle{v^{(i)}},{P}\rangle-\langle{v^{(i)}},{x}\rangle\right|$
$\displaystyle\geq\left|\langle{v^{(i)}},{P}\rangle+\langle{v-v^{(i)}},{x}\rangle-t\right|-|\langle{v},{x}\rangle-t|$
$\displaystyle>\sigma\|{v^{(i)}}\|_{2}-2|v_{k}|\geq(\sigma-2)\|{v^{(i)}}\|_{2},$

by the triangle inequality. Using again the fact that under conditioning of
the value of $P$, the $K(i)$ coordinates of $x$ are independent of $E_{2}$,
together with Hoeffding’s inequality, we deduce

$\displaystyle\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,E_{2}\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{P}\left[\Pr\left[|\langle{v},{x}\rangle-t|<2|v_{k}|\,\middle|\,E_{2},P\right]\right]$
$\displaystyle=\operatorname*{\mathbb{E}}_{P}\left[\Pr\left[\left|\langle{v^{(i)}},{P}\rangle-\langle{v^{(i)}},{x}\rangle\right|>(\sigma-2)\|{v^{(i)}}\|_{2}\,\middle|\,P\right]\right]$
$\displaystyle\leq 2\exp(-(\sigma-2)^{2}/2)=2/n^{2}.$

This concludes the proof of (11).

Proving (12). Unlike the rest of the proof, we henceforth assume that $P$ has
the exact same distribution as in Definition (2.2), and we are explicit about
the conditioning on $\|{P}\|_{\infty}\leq 1/2$.

Let $F^{\prime}$ be the event that $\\{\|{P}\|_{\infty}\leq 1/2\\}$ and let
$F$ be the event that $\\{\|{P}\|_{\infty,[n]\setminus K(i)}\leq 1/2\\}$,
meaning that all coordinates of $P$ except those in $K(i)$ are less than $1/2$
in absolute value.

In (12) we seek to bound $\Pr\left[\neg{E}\,\middle|\,F^{\prime}\right]$.
However, it is more convenient to bound $\Pr\left[\neg{E}\,\middle|\,F\right]$
instead. There is not much loss in doing so, in virtue of Lemma 2.3 and that
$F^{\prime}\subseteq F$:

$\Pr\left[\neg{E}\,\middle|\,F^{\prime}\right]=\frac{\Pr\left[\neg{E}\wedge
F^{\prime}\right]}{\Pr[F^{\prime}]}\leq\frac{\Pr\left[\neg{E}\wedge
F\right]}{(1-2/n)\Pr[F]}\leq O(\Pr\left[\neg{E}\,\middle|\,F\right]).$

Thus (12) is reduced to

$\Pr\left[\neg{E}\,\middle|\,F\right]\leq
O\left(2^{-r}\sigma\sqrt{\frac{m\log(n)}{|K({i})|}}\right)$ (16)

The estimate (16) follows by that $E=E_{1}\cup E_{2}$ hence
$\Pr\left[\neg{E}\,\middle|\,F\right]=\Pr\left[\neg{E_{1}}\,\middle|\,F\right]\Pr\left[\neg{E_{2}}\,\middle|\,F,\neg{E_{1}}\right]$,
and

$\Pr\left[\neg{E_{1}}\,\middle|\,F\right]\leq O(2^{-r}),$ (17)
$\Pr\left[\neg{E_{2}}\,\middle|\,F,\neg{E_{1}}\right]\leq
O\left(\sigma\sqrt{\frac{m\log(n)}{|K({i})|}}\right).$ (18)

To confirm (17) we use Lemma 2.14. Denote
$\alpha\mathrel{\mathop{:}}=3\|{v^{(i)}}\|_{1}$ and note $\alpha\leq 3n\cdot
2^{-i}$. Recalling the definition of $r$, we see that there are at least
$2(r-1)\log(n)$ elements $j\in J$ with $2^{-j-1}\geq\alpha$. Hence (6) reads
as $Q(\alpha,X_{u,P})\leq O(2^{1-r})$ with $u=v-v^{(i)}$, thus implying (17).

In order to prove (18) we recall that by definition 2.2

$\begin{gathered}P=\frac{1}{10\sqrt{\log(n)}}\sum_{\ell=1}^{m}\sum_{j\in
J_{\ell}}\alpha_{\ell j}\frac{2^{j}}{\sqrt{m}}\bar{v}_{\ell}^{(j)},\\\
(\neg{E_{2}})=\left\\{|\langle{v-v^{(i)}},{x}\rangle+\langle{v^{(i)}},{P}\rangle-t|<\sigma\|{v^{(i)}}\|_{2}\right\\},\end{gathered}$

with $\alpha_{\ell j}\sim U([-1,1])$. Roughly speaking, we show that the
random variable $\langle{v^{(i)}},{P}\rangle$ has a significant variance, and
hence $\neg{E_{2}}$ is a rare event.

Fix (that is, condition on) any value of $\alpha_{\ell j}$ whenever
$(\ell,j)\neq(1,i)$ (recall $v=\bar{v}_{1}$) and on all coordinates of $x$
that are outside $K(i)$. Observe that the occurrence of the events $E_{1}$ and
$F$ is determined by this fixing. However, since $\alpha_{1i}$ is independent
of all other $\alpha_{\ell j}$, and it affects only the $K(i)$ coordinates of
$P$ (hence is independent also of $F$ and $E_{1}$), $\alpha_{1i}$ is still
uniformly distributed in $[-1,1]$. Hence, the following is a variable which is
uniformly distributed in some real interval

$\langle{v^{(i)}},{P}\rangle=\alpha_{1i}\frac{2^{i}}{10\sqrt{m\log(n)}}\langle{v^{(i)}},{v^{(i)}}\rangle+\rho,$
(19)

with $\rho\in\mathbb{R}$ a constant depending on the fixing. Note that by
definition of binary decomposition, $v^{(i)}$ has $K(i)$ nonzero coordinates,
all having absolute values in the range $(2^{-i-1},2^{-i}]$. Hence
$\|{v^{(i)}}\|_{2}^{2}=\Theta(|K(i)|4^{-i})$. Overall, the probability that
$\neg{E_{2}}$ happens – which means that $\langle{v^{(i)}},{P}\rangle$ is only
$\sigma\|{v^{(i)}}\|_{2}$ away from the constant
$(t-\langle{v-v^{(i)}},{x}\rangle)$ – is bounded by the anti-concentration of
the uniform variable (19):

$\Pr\left[\neg{E_{2}}\,\middle|\,F,\neg{E_{1}}\right]\leq\frac{\sigma\|{v^{(i)}}\|_{2}}{\frac{2^{i}}{10\sqrt{m\log(n)}}\langle{v^{(i)}},{v^{(i)}}\rangle}=\frac{10\sigma\sqrt{m\log(n)}}{2^{i}\|{v^{(i)}}\|_{2}}=\frac{10\sigma\sqrt{m}{\log(n)}}{\sqrt{|K(i)|}},$

yielding (18) and concluding the proof. ∎

## Acknowledgements

The author is grateful to Nathan Keller for matchmaking him with the problem.
I thank Yiting Wang for spotting an inaccuracy in an earlier version of this
paper. The help of Yotam Shomroni regarding the presentation is highly
appreciated.

## References

  * [1] K. Ball, The plank problem for symmetric bodies, Invent. math. 104 (1991), pp. 535–543.
  * [2] B. Grünbaum, How to cut all edges of a polytope? Amer. Math. Monthly 89(8) (1972), pp. 890–895.
  * [3] W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58(301) (1963), pp. 13–30.
  * [4] P. E. O’Neil, Hyperplane cuts of an $n$-cube. Discrete Mathematics 1(2) (1971), pp. 193–195.
  * [5] B. A. Rogozin, An Estimate for Concentration Functions, Theory Probab. Appl. 6 (1961), pp. 94–97.
  * [6] M. E. Saks, Slicing the hypercube, in: Surveys in Combin. 14 (1993), Cambridge University Press, pp. 211–256.
  * [7] E. Sperner, Ein Satz über Untermengen einer endlichen Menge, Mathematische Zeitschrift 27(1) (1928), pp. 544–548.
  * [8] R. Titsworth, Correlation properties of cyclic sequences, PhD thesis, California Institute of Technology, 1962.
  * [9] G. Yehuda and A. Yehudayoff, Slicing The Hypercube is not Easy, 2021. Available at ArXiv:2102.05536.

##  Appendix A Proofs of standard facts

###### Proof of Lemma 2.3.

Consider $P_{i}$, it is a random variable equal to

$\frac{1}{10\sqrt{m\log(n)}}\sum_{\ell=1}^{m}\alpha_{\ell}v_{\ell i}^{\prime}$

with $v_{\ell i}^{\prime}\in(1/2,1]$ being $v_{\ell i}$ multiplied by an
integral power of 2, and $\alpha_{\ell}\sim U([-1,1])$. Note that each
$\alpha_{\ell}$ may be implemented as $\sum_{j=1}^{\infty}2^{-j}x_{j}$ with
$x_{j}\sim\left\\{-1,1\right\\}$ uniformly and independently. If we hence
aggregate an infinite vector $u=(2^{-j}v_{\ell
i}^{\prime})_{\ell=1,j=1}^{m,\infty}$, then $P_{i}$ has the distribution of
$\frac{1}{10\sqrt{m\log(n)}}\langle{u},{x}\rangle$ with all
$x_{i}\sim\left\\{-1,1\right\\}$ independently and uniformly distributed. Note
also that $\|{u}\|_{2}=\sum_{\ell=1}^{m}v_{\ell i}^{\prime 2}/3\leq m/3$.
Therefore, Claim 2.10 implies

$\Pr_{\alpha}[|P_{i}|\geq 1/2]=\Pr_{x}[|\langle{u},{x}\rangle|\geq
5\sqrt{m\log(n)}]\leq\Pr_{x}[|\langle{u},{x}\rangle|\geq
8\|{u}\|_{2}\sqrt{\log(n)}]\leq 2/n^{32}.$

Union bound implies that $\|{P}\|_{\infty}\leq 1/2$ except for probability
$2/n^{31}$. ∎

###### Proof of Lemma 2.13.

Case $p=\underline{0}$. In this case $X_{v,p}=\sum_{i=1}^{n}x_{i}v_{i}$ with
the $x_{i}$’s uniformly and independently distributed in
$\left\\{-1,1\right\\}$. Without loss of generality we may assume $v_{i}\geq
0$ for all $i$. For any $t\in\mathbb{R}$ the set of $x$’s for which
$|X_{v,p}-t|<\alpha$ corresponds to an anti-chain in every subcube of
$\left\\{-1,1\right\\}^{n}$, generated by the $[a]$ coordinates. Sperner’s
theorem [7] hence implies $\Pr[|X_{v,p}-t|<\alpha]\leq\binom{a}{\lfloor
a/2\rceil}/2^{a}=O(1/\sqrt{a})$, yielding $Q(\alpha,X_{v,p})\leq
O(1/\sqrt{a})$.

Case $\|{p}\|_{\infty}\leq 1/2$. We present $X_{v,p}$ as a mixture of random
variables $X_{v^{\prime},p^{\prime}}$ with $p^{\prime}=\underline{0}$, and
with $v^{\prime}$ usually having $\Omega(a)$ coordinates $\geq a$, and the
previous case of the proof.

Indeed, choose $v^{\prime}$ to be $v$ with each coordinate $i$ zeroed out
independently with probability $|p_{i}|$. If $v_{i}^{\prime}$ was zeroed out,
choose $\rho_{i}$ to be $v_{i}\cdot\frac{p_{i}}{|p_{i}|}$, otherwise (or if
$p_{i}=0$) – $\rho_{i}=0$. We note that if $x\sim\mu_{p}$ and
$x^{\prime}\sim\mu_{\underline{0}}$, then $v_{i}\cdot x_{i}$ can be realized
as $\rho_{i}+v_{i}^{\prime}\cdot x^{\prime}_{i}$ – the excess probability
associated with one of the outcomes of $x_{i}\in\left\\{-1,1\right\\}$ is
simulated through $\rho_{i}$.

We conclude that the distribution of $X_{v,p}$ can be sampled by first drawing
$v^{\prime},\rho$ and then sampling $\sum_{i}v_{i}^{\prime}\cdot
x^{\prime}_{i}+\sum_{i}\rho_{i}$. In particular,

$Q(\alpha,X_{v,p})\leq\operatorname*{\mathbb{E}}[Q(\alpha,X_{v^{\prime},\underline{0}})]\leq\operatorname*{\mathbb{E}}[\min(O(1/\sqrt{a^{\prime}}),1)],$
(20)

with $a^{\prime}$ the number of coordinates $k$ with
$|v^{\prime}_{k}|\geq\alpha$. By definition of $v^{\prime}$, $a^{\prime}$ is
distributed as a sum of $a$ Bernoulli random variables, the $i$’th of which
having success probability $1-|p_{i}|$. Since $|p_{i}|\leq 1/2$, we have
$\operatorname*{\mathbb{E}}[a^{\prime}]\geq a/2$. Moreover, the distribution
of $a^{\prime}$ is quite concentrated around
$\operatorname*{\mathbb{E}}[a^{\prime}]$, with Chebyshev’s inequality implying
that $\Pr[a^{\prime}<a/4]\leq 4/a$. This with (20) give

$Q(\alpha,X_{v,p})\leq
O(\operatorname*{\mathbb{E}}[\min(1/\sqrt{a^{\prime}},1)])\leq
O(1/\sqrt{a/4}+4/a)=O(1/\sqrt{a}).$

∎