Slicing the hypercube is not easy Article Swipe

PDF

YOU? · · 2021 · Open Access · · DOI: https://doi.org/10.48550/arxiv.2102.05536

We prove that at least $Ω(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.

Related Topics

Mathematical Analysis

Concepts

Hypercube Hyperplane Slicing Skew Upper and lower bounds Computer science Combinatorics Computational complexity theory Parallel computing Discrete mathematics Mathematics Algorithm World Wide Web Telecommunications Mathematical analysis

Metadata

Type: preprint
Language: en
Landing Page: http://arxiv.org/abs/2102.05536
PDF: https://arxiv.org/pdf/2102.05536
OA Status: green
Cited By: 4
References: 23
Related Works: 10
OpenAlex ID: https://openalex.org/W3128839604

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W3128839604

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.48550/arxiv.2102.05536

Digital Object Identifier
Title: Slicing the hypercube is not easy

Work title
Type: preprint

OpenAlex work type
Language: en

Primary language
Publication year: 2021

Year of publication
Publication date: 2021-02-10

Full publication date if available
Authors: Gal Yehuda, Amir Yehudayoff

List of authors in order
Landing page: https://arxiv.org/abs/2102.05536

Publisher landing page
PDF URL: https://arxiv.org/pdf/2102.05536

Direct link to full text PDF
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://arxiv.org/pdf/2102.05536

Direct OA link when available
Concepts: Hypercube, Hyperplane, Slicing, Skew, Upper and lower bounds, Computer science, Combinatorics, Computational complexity theory, Parallel computing, Discrete mathematics, Mathematics, Algorithm, World Wide Web, Telecommunications, Mathematical analysis

Top concepts (fields/topics) attached by OpenAlex
Cited by: 4

Total citation count in OpenAlex
Citations by year (recent): 2024: 1, 2023: 1, 2022: 1, 2021: 1

Per-year citation counts (last 5 years)
References (count): 23

Number of works referenced by this work
Related works (count): 10

Other works algorithmically related by OpenAlex

Full payload

id	https://openalex.org/W3128839604
doi	https://doi.org/10.48550/arxiv.2102.05536
ids.doi	https://doi.org/10.48550/arxiv.2102.05536
ids.mag	3128839604
ids.openalex	https://openalex.org/W3128839604
fwci
type	preprint
title	Slicing the hypercube is not easy
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10374
topics[0].field.id	https://openalex.org/fields/17
topics[0].field.display_name	Computer Science
topics[0].score	0.9994999766349792
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/1703
topics[0].subfield.display_name	Computational Theory and Mathematics
topics[0].display_name	Advanced Graph Theory Research
topics[1].id	https://openalex.org/T10829
topics[1].field.id	https://openalex.org/fields/17
topics[1].field.display_name	Computer Science
topics[1].score	0.9990000128746033
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/1705
topics[1].subfield.display_name	Computer Networks and Communications
topics[1].display_name	Interconnection Networks and Systems
topics[2].id	https://openalex.org/T11797
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.9980000257492065
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2208
topics[2].subfield.display_name	Electrical and Electronic Engineering
topics[2].display_name	graph theory and CDMA systems
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C50820777
concepts[0].level	2
concepts[0].score	0.9397710561752319
concepts[0].wikidata	https://www.wikidata.org/wiki/Q213723
concepts[0].display_name	Hypercube
concepts[1].id	https://openalex.org/C68693459
concepts[1].level	2
concepts[1].score	0.8486950397491455
concepts[1].wikidata	https://www.wikidata.org/wiki/Q657586
concepts[1].display_name	Hyperplane
concepts[2].id	https://openalex.org/C2776190703
concepts[2].level	2
concepts[2].score	0.7066925764083862
concepts[2].wikidata	https://www.wikidata.org/wiki/Q488148
concepts[2].display_name	Slicing
concepts[3].id	https://openalex.org/C43711488
concepts[3].level	2
concepts[3].score	0.5817825794219971
concepts[3].wikidata	https://www.wikidata.org/wiki/Q7534783
concepts[3].display_name	Skew
concepts[4].id	https://openalex.org/C77553402
concepts[4].level	2
concepts[4].score	0.5448737740516663
concepts[4].wikidata	https://www.wikidata.org/wiki/Q13222579
concepts[4].display_name	Upper and lower bounds
concepts[5].id	https://openalex.org/C41008148
concepts[5].level	0
concepts[5].score	0.5393050312995911
concepts[5].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[5].display_name	Computer science
concepts[6].id	https://openalex.org/C114614502
concepts[6].level	1
concepts[6].score	0.5042165517807007
concepts[6].wikidata	https://www.wikidata.org/wiki/Q76592
concepts[6].display_name	Combinatorics
concepts[7].id	https://openalex.org/C179799912
concepts[7].level	2
concepts[7].score	0.42426615953445435
concepts[7].wikidata	https://www.wikidata.org/wiki/Q205084
concepts[7].display_name	Computational complexity theory
concepts[8].id	https://openalex.org/C173608175
concepts[8].level	1
concepts[8].score	0.41976991295814514
concepts[8].wikidata	https://www.wikidata.org/wiki/Q232661
concepts[8].display_name	Parallel computing
concepts[9].id	https://openalex.org/C118615104
concepts[9].level	1
concepts[9].score	0.3536817133426666
concepts[9].wikidata	https://www.wikidata.org/wiki/Q121416
concepts[9].display_name	Discrete mathematics
concepts[10].id	https://openalex.org/C33923547
concepts[10].level	0
concepts[10].score	0.3360671401023865
concepts[10].wikidata	https://www.wikidata.org/wiki/Q395
concepts[10].display_name	Mathematics
concepts[11].id	https://openalex.org/C11413529
concepts[11].level	1
concepts[11].score	0.24396559596061707
concepts[11].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[11].display_name	Algorithm
concepts[12].id	https://openalex.org/C136764020
concepts[12].level	1
concepts[12].score	0.0
concepts[12].wikidata	https://www.wikidata.org/wiki/Q466
concepts[12].display_name	World Wide Web
concepts[13].id	https://openalex.org/C76155785
concepts[13].level	1
concepts[13].score	0.0
concepts[13].wikidata	https://www.wikidata.org/wiki/Q418
concepts[13].display_name	Telecommunications
concepts[14].id	https://openalex.org/C134306372
concepts[14].level	1
concepts[14].score	0.0
concepts[14].wikidata	https://www.wikidata.org/wiki/Q7754
concepts[14].display_name	Mathematical analysis
keywords[0].id	https://openalex.org/keywords/hypercube
keywords[0].score	0.9397710561752319
keywords[0].display_name	Hypercube
keywords[1].id	https://openalex.org/keywords/hyperplane
keywords[1].score	0.8486950397491455
keywords[1].display_name	Hyperplane
keywords[2].id	https://openalex.org/keywords/slicing
keywords[2].score	0.7066925764083862
keywords[2].display_name	Slicing
keywords[3].id	https://openalex.org/keywords/skew
keywords[3].score	0.5817825794219971
keywords[3].display_name	Skew
keywords[4].id	https://openalex.org/keywords/upper-and-lower-bounds
keywords[4].score	0.5448737740516663
keywords[4].display_name	Upper and lower bounds
keywords[5].id	https://openalex.org/keywords/computer-science
keywords[5].score	0.5393050312995911
keywords[5].display_name	Computer science
keywords[6].id	https://openalex.org/keywords/combinatorics
keywords[6].score	0.5042165517807007
keywords[6].display_name	Combinatorics
keywords[7].id	https://openalex.org/keywords/computational-complexity-theory
keywords[7].score	0.42426615953445435
keywords[7].display_name	Computational complexity theory
keywords[8].id	https://openalex.org/keywords/parallel-computing
keywords[8].score	0.41976991295814514
keywords[8].display_name	Parallel computing
keywords[9].id	https://openalex.org/keywords/discrete-mathematics
keywords[9].score	0.3536817133426666
keywords[9].display_name	Discrete mathematics
keywords[10].id	https://openalex.org/keywords/mathematics
keywords[10].score	0.3360671401023865
keywords[10].display_name	Mathematics
keywords[11].id	https://openalex.org/keywords/algorithm
keywords[11].score	0.24396559596061707
keywords[11].display_name	Algorithm
language	en
locations[0].id	pmh:oai:arXiv.org:2102.05536
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306400194
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	True
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	arXiv (Cornell University)
locations[0].source.host_organization	https://openalex.org/I205783295
locations[0].source.host_organization_name	Cornell University
locations[0].source.host_organization_lineage	https://openalex.org/I205783295
locations[0].license
locations[0].pdf_url	https://arxiv.org/pdf/2102.05536
locations[0].version	submittedVersion
locations[0].raw_type	text
locations[0].license_id
locations[0].is_accepted	False
locations[0].is_published	False
locations[0].raw_source_name
locations[0].landing_page_url	http://arxiv.org/abs/2102.05536
locations[1].id	doi:10.48550/arxiv.2102.05536
locations[1].is_oa	True
locations[1].source.id	https://openalex.org/S4306400194
locations[1].source.issn
locations[1].source.type	repository
locations[1].source.is_oa	True
locations[1].source.issn_l
locations[1].source.is_core	False
locations[1].source.is_in_doaj	False
locations[1].source.display_name	arXiv (Cornell University)
locations[1].source.host_organization	https://openalex.org/I205783295
locations[1].source.host_organization_name	Cornell University
locations[1].source.host_organization_lineage	https://openalex.org/I205783295
locations[1].license	cc-by
locations[1].pdf_url
locations[1].version
locations[1].raw_type	article
locations[1].license_id	https://openalex.org/licenses/cc-by
locations[1].is_accepted	False
locations[1].is_published
locations[1].raw_source_name
locations[1].landing_page_url	https://doi.org/10.48550/arxiv.2102.05536
indexed_in	arxiv, datacite
authorships[0].author.id	https://openalex.org/A5082992148
authorships[0].author.orcid
authorships[0].author.display_name	Gal Yehuda
authorships[0].author_position	first
authorships[0].raw_author_name	Gal Yehuda
authorships[0].is_corresponding	False
authorships[1].author.id	https://openalex.org/A5041051779
authorships[1].author.orcid	https://orcid.org/0000-0002-0177-1814
authorships[1].author.display_name	Amir Yehudayoff
authorships[1].author_position	last
authorships[1].raw_author_name	Amir Yehudayoff
authorships[1].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://arxiv.org/pdf/2102.05536
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-10-10T00:00:00
display_name	Slicing the hypercube is not easy
has_fulltext	False
is_retracted	False
updated_date	2025-11-06T06:51:31.235846
primary_topic.id	https://openalex.org/T10374
primary_topic.field.id	https://openalex.org/fields/17
primary_topic.field.display_name	Computer Science
primary_topic.score	0.9994999766349792
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/1703
primary_topic.subfield.display_name	Computational Theory and Mathematics
primary_topic.display_name	Advanced Graph Theory Research
related_works	https://openalex.org/W2393746923, https://openalex.org/W2972496411, https://openalex.org/W4239223006, https://openalex.org/W2369655046, https://openalex.org/W3033662781, https://openalex.org/W2137530048, https://openalex.org/W2360869927, https://openalex.org/W2050876785, https://openalex.org/W2213934937, https://openalex.org/W3022636680
cited_by_count	4
counts_by_year[0].year	2024
counts_by_year[0].cited_by_count	1
counts_by_year[1].year	2023
counts_by_year[1].cited_by_count	1
counts_by_year[2].year	2022
counts_by_year[2].cited_by_count	1
counts_by_year[3].year	2021
counts_by_year[3].cited_by_count	1
locations_count	2
best_oa_location.id	pmh:oai:arXiv.org:2102.05536
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306400194
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	True
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	arXiv (Cornell University)
best_oa_location.source.host_organization	https://openalex.org/I205783295
best_oa_location.source.host_organization_name	Cornell University
best_oa_location.source.host_organization_lineage	https://openalex.org/I205783295
best_oa_location.license
best_oa_location.pdf_url	https://arxiv.org/pdf/2102.05536
best_oa_location.version	submittedVersion
best_oa_location.raw_type	text
best_oa_location.license_id
best_oa_location.is_accepted	False
best_oa_location.is_published	False
best_oa_location.raw_source_name
best_oa_location.landing_page_url	http://arxiv.org/abs/2102.05536
primary_location.id	pmh:oai:arXiv.org:2102.05536
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306400194
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	True
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	arXiv (Cornell University)
primary_location.source.host_organization	https://openalex.org/I205783295
primary_location.source.host_organization_name	Cornell University
primary_location.source.host_organization_lineage	https://openalex.org/I205783295
primary_location.license
primary_location.pdf_url	https://arxiv.org/pdf/2102.05536
primary_location.version	submittedVersion
primary_location.raw_type	text
primary_location.license_id
primary_location.is_accepted	False
primary_location.is_published	False
primary_location.raw_source_name
primary_location.landing_page_url	http://arxiv.org/abs/2102.05536
publication_date	2021-02-10
publication_year	2021
referenced_works	https://openalex.org/W2052840523, https://openalex.org/W3099738159, https://openalex.org/W2900463864, https://openalex.org/W2014485295, https://openalex.org/W2084913436, https://openalex.org/W2001187993, https://openalex.org/W1992785361, https://openalex.org/W2143702634, https://openalex.org/W1891181203, https://openalex.org/W2073286344, https://openalex.org/W2015732351, https://openalex.org/W24307859, https://openalex.org/W2087567316, https://openalex.org/W2011247844, https://openalex.org/W2139266282, https://openalex.org/W2057763516, https://openalex.org/W1970189297, https://openalex.org/W2147786227, https://openalex.org/W2035175249, https://openalex.org/W2168115971, https://openalex.org/W2063165065, https://openalex.org/W2103749128, https://openalex.org/W2146415227
referenced_works_count	23
abstract_inverted_index.a	19, 32
abstract_inverted_index.We	0, 17
abstract_inverted_index.at	3
abstract_inverted_index.by	42
abstract_inverted_index.of	13, 21, 29, 39
abstract_inverted_index.on	25, 35
abstract_inverted_index.to	9
abstract_inverted_index.all	11
abstract_inverted_index.and	31
abstract_inverted_index.are	7
abstract_inverted_index.the	14, 26, 36, 40
abstract_inverted_index.skew	43
abstract_inverted_index.that	2
abstract_inverted_index.bound	34
abstract_inverted_index.cover	37
abstract_inverted_index.edges	12
abstract_inverted_index.least	4
abstract_inverted_index.lower	23, 33
abstract_inverted_index.prove	1
abstract_inverted_index.slice	10
abstract_inverted_index.bounds	24
abstract_inverted_index.couple	20
abstract_inverted_index.needed	8
abstract_inverted_index.number	38
abstract_inverted_index.parity,	30
abstract_inverted_index.provide	18
abstract_inverted_index.hypercube	41
abstract_inverted_index.complexity	28
abstract_inverted_index.hypercube.	16
abstract_inverted_index.hyperplanes	6
abstract_inverted_index.hyperplanes.	44
abstract_inverted_index.applications:	22
abstract_inverted_index.computational	27
abstract_inverted_index.$Ω(n^{0.51})$	5
abstract_inverted_index.$n$-dimensional	15
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	2
citation_normalized_percentile