Slicing the hypercube is not easy
We prove that at least $\Omega(n^{0.51})$ hyperplanes are needed to slice all edges of the $n$-dimensional hypercube. We provide a couple of applications: lower bounds on the computational complexity of parity, and a lower bound on the cover number of the hypercube by skew hyperplanes.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Improved Upper Bounds for Slicing the Hypercube
A collection of hyperplanes $\mathcal{H}$ slices all edges of the $n$-dimensional hypercube $Q_n$ with vertex set $\{-1,1\}^n$ if, for every edge $e$ in the hypercube, there exists a hyperplane in $\mathcal{H}$ intersect…
Hypercube-RAG: Hypercube-Based Retrieval-Augmented Generation for In-domain Scientific Question-Answering
Large language models (LLMs) often need to incorporate external knowledge to solve theme-specific problems. Retrieval-augmented generation (RAG), which empowers LLMs to generate more qualified responses with retrieved ex…
Question AnsweringRAGRetrievalRetrieval-augmented Generation+2A Note on Small Percolating Sets on Hypercubes via Generative AI
We apply a generative AI pattern-recognition technique called PatternBoost to study bootstrap percolation on hypercubes. With this, we slightly improve the best existing upper bound for the size of percolating subsets of…
Evaluation of YOLO Models with Sliced Inference for Small Object Detection
Small object detection has major applications in the fields of UAVs, surveillance, farming and many others. In this work we investigate the performance of state of the art Yolo based object detection models for the task …
Objectobject-detectionObject DetectionSmall Object DetectionAI-Native Network Slicing for 6G Networks
With the global roll-out of the fifth generation (5G) networks, it is necessary to look beyond 5G and envision the 6G networks. The 6G networks are expected to have space-air-ground integrated networks, advanced network …
Management