Instance complexity of Boolean functions Article Swipe
Hsiang-Hsuan Liu
,
Nikhil S. Mande
·
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2309.15026
YOU?
·
· 2023
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2309.15026
In the area of query complexity of Boolean functions, the most widely studied cost measure of an algorithm is the worst-case number of queries made by it on an input. Motivated by the most natural cost measure studied in online algorithms, the competitive ratio, we consider a different cost measure for query algorithms for Boolean functions that captures the ratio of the cost of the algorithm and the cost of an optimal algorithm that knows the input in advance. The cost of an algorithm is its largest cost over all inputs. Grossman, Komargodski and Naor [ITCS'20] introduced this measure for Boolean functions, and dubbed it instance complexity. Grossman et al. showed, among other results, that monotone Boolean functions with instance complexity 1 are precisely those that depend on one or two variables. We complement the above-mentioned result of Grossman et al. by completely characterizing the instance complexity of symmetric Boolean functions. As a corollary we conclude that the only symmetric Boolean functions with instance complexity 1 are the Parity function and its complement. We also study the instance complexity of some graph properties like Connectivity and k-clique containment. In all the Boolean functions we study above, and those studied by Grossman et al., the instance complexity turns out to be the ratio of query complexity to minimum certificate complexity. It is a natural question to ask if this is the correct bound for all Boolean functions. We show a negative answer in a very strong sense, by analyzing the instance complexity of the Greater-Than and Odd-Max-Bit functions. We show that the above-mentioned ratio is linear in the input size for both of these functions, while we exhibit algorithms for which the instance complexity is a constant.
Related Topics
Concepts
Boolean function
Complexity index
Complement (music)
Boolean circuit
Mathematics
Discrete mathematics
Parity function
Time complexity
Worst-case complexity
Boolean network
Boolean expression
Combinatorics
Clique
Theoretical computer science
Computer science
Gene
Chemistry
Complementation
Biochemistry
Phenotype
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2309.15026
- https://arxiv.org/pdf/2309.15026
- OA Status
- green
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4387156631
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4387156631Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2309.15026Digital Object Identifier
- Title
-
Instance complexity of Boolean functionsWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2023Year of publication
- Publication date
-
2023-09-26Full publication date if available
- Authors
-
Hsiang-Hsuan Liu, Nikhil S. MandeList of authors in order
- Landing page
-
https://arxiv.org/abs/2309.15026Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2309.15026Direct link to full text PDF
- Open access
-
YesWhether a free full text is available
- OA status
-
greenOpen access status per OpenAlex
- OA URL
-
https://arxiv.org/pdf/2309.15026Direct OA link when available
- Concepts
-
Boolean function, Complexity index, Complement (music), Boolean circuit, Mathematics, Discrete mathematics, Parity function, Time complexity, Worst-case complexity, Boolean network, Boolean expression, Combinatorics, Clique, Theoretical computer science, Computer science, Gene, Chemistry, Complementation, Biochemistry, PhenotypeTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
0Total citation count in OpenAlex
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4387156631 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2309.15026 |
| ids.doi | https://doi.org/10.48550/arxiv.2309.15026 |
| ids.openalex | https://openalex.org/W4387156631 |
| fwci | |
| type | preprint |
| title | Instance complexity of Boolean functions |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T12072 |
| topics[0].field.id | https://openalex.org/fields/17 |
| topics[0].field.display_name | Computer Science |
| topics[0].score | 0.9958999752998352 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/1702 |
| topics[0].subfield.display_name | Artificial Intelligence |
| topics[0].display_name | Machine Learning and Algorithms |
| topics[1].id | https://openalex.org/T11269 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9908000230789185 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1702 |
| topics[1].subfield.display_name | Artificial Intelligence |
| topics[1].display_name | Algorithms and Data Compression |
| topics[2].id | https://openalex.org/T12288 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9882000088691711 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1705 |
| topics[2].subfield.display_name | Computer Networks and Communications |
| topics[2].display_name | Optimization and Search Problems |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C187455244 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6811496019363403 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q942353 |
| concepts[0].display_name | Boolean function |
| concepts[1].id | https://openalex.org/C6435147 |
| concepts[1].level | 3 |
| concepts[1].score | 0.6375360488891602 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q5156627 |
| concepts[1].display_name | Complexity index |
| concepts[2].id | https://openalex.org/C112313634 |
| concepts[2].level | 5 |
| concepts[2].score | 0.6121652126312256 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q7886648 |
| concepts[2].display_name | Complement (music) |
| concepts[3].id | https://openalex.org/C141796577 |
| concepts[3].level | 3 |
| concepts[3].score | 0.5614409446716309 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q837479 |
| concepts[3].display_name | Boolean circuit |
| concepts[4].id | https://openalex.org/C33923547 |
| concepts[4].level | 0 |
| concepts[4].score | 0.5457141399383545 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[4].display_name | Mathematics |
| concepts[5].id | https://openalex.org/C118615104 |
| concepts[5].level | 1 |
| concepts[5].score | 0.5115635991096497 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q121416 |
| concepts[5].display_name | Discrete mathematics |
| concepts[6].id | https://openalex.org/C188183281 |
| concepts[6].level | 4 |
| concepts[6].score | 0.5020737648010254 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q2898309 |
| concepts[6].display_name | Parity function |
| concepts[7].id | https://openalex.org/C311688 |
| concepts[7].level | 2 |
| concepts[7].score | 0.44606131315231323 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2393193 |
| concepts[7].display_name | Time complexity |
| concepts[8].id | https://openalex.org/C96563100 |
| concepts[8].level | 3 |
| concepts[8].score | 0.44485774636268616 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8037118 |
| concepts[8].display_name | Worst-case complexity |
| concepts[9].id | https://openalex.org/C134444547 |
| concepts[9].level | 3 |
| concepts[9].score | 0.4391269385814667 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q585230 |
| concepts[9].display_name | Boolean network |
| concepts[10].id | https://openalex.org/C158465420 |
| concepts[10].level | 3 |
| concepts[10].score | 0.43886905908584595 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q1979515 |
| concepts[10].display_name | Boolean expression |
| concepts[11].id | https://openalex.org/C114614502 |
| concepts[11].level | 1 |
| concepts[11].score | 0.4154568910598755 |
| concepts[11].wikidata | https://www.wikidata.org/wiki/Q76592 |
| concepts[11].display_name | Combinatorics |
| concepts[12].id | https://openalex.org/C2777035058 |
| concepts[12].level | 2 |
| concepts[12].score | 0.41389793157577515 |
| concepts[12].wikidata | https://www.wikidata.org/wiki/Q1662634 |
| concepts[12].display_name | Clique |
| concepts[13].id | https://openalex.org/C80444323 |
| concepts[13].level | 1 |
| concepts[13].score | 0.3938550651073456 |
| concepts[13].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[13].display_name | Theoretical computer science |
| concepts[14].id | https://openalex.org/C41008148 |
| concepts[14].level | 0 |
| concepts[14].score | 0.3331069350242615 |
| concepts[14].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[14].display_name | Computer science |
| concepts[15].id | https://openalex.org/C104317684 |
| concepts[15].level | 2 |
| concepts[15].score | 0.0 |
| concepts[15].wikidata | https://www.wikidata.org/wiki/Q7187 |
| concepts[15].display_name | Gene |
| concepts[16].id | https://openalex.org/C185592680 |
| concepts[16].level | 0 |
| concepts[16].score | 0.0 |
| concepts[16].wikidata | https://www.wikidata.org/wiki/Q2329 |
| concepts[16].display_name | Chemistry |
| concepts[17].id | https://openalex.org/C188082640 |
| concepts[17].level | 4 |
| concepts[17].score | 0.0 |
| concepts[17].wikidata | https://www.wikidata.org/wiki/Q1780899 |
| concepts[17].display_name | Complementation |
| concepts[18].id | https://openalex.org/C55493867 |
| concepts[18].level | 1 |
| concepts[18].score | 0.0 |
| concepts[18].wikidata | https://www.wikidata.org/wiki/Q7094 |
| concepts[18].display_name | Biochemistry |
| concepts[19].id | https://openalex.org/C127716648 |
| concepts[19].level | 3 |
| concepts[19].score | 0.0 |
| concepts[19].wikidata | https://www.wikidata.org/wiki/Q104053 |
| concepts[19].display_name | Phenotype |
| keywords[0].id | https://openalex.org/keywords/boolean-function |
| keywords[0].score | 0.6811496019363403 |
| keywords[0].display_name | Boolean function |
| keywords[1].id | https://openalex.org/keywords/complexity-index |
| keywords[1].score | 0.6375360488891602 |
| keywords[1].display_name | Complexity index |
| keywords[2].id | https://openalex.org/keywords/complement |
| keywords[2].score | 0.6121652126312256 |
| keywords[2].display_name | Complement (music) |
| keywords[3].id | https://openalex.org/keywords/boolean-circuit |
| keywords[3].score | 0.5614409446716309 |
| keywords[3].display_name | Boolean circuit |
| keywords[4].id | https://openalex.org/keywords/mathematics |
| keywords[4].score | 0.5457141399383545 |
| keywords[4].display_name | Mathematics |
| keywords[5].id | https://openalex.org/keywords/discrete-mathematics |
| keywords[5].score | 0.5115635991096497 |
| keywords[5].display_name | Discrete mathematics |
| keywords[6].id | https://openalex.org/keywords/parity-function |
| keywords[6].score | 0.5020737648010254 |
| keywords[6].display_name | Parity function |
| keywords[7].id | https://openalex.org/keywords/time-complexity |
| keywords[7].score | 0.44606131315231323 |
| keywords[7].display_name | Time complexity |
| keywords[8].id | https://openalex.org/keywords/worst-case-complexity |
| keywords[8].score | 0.44485774636268616 |
| keywords[8].display_name | Worst-case complexity |
| keywords[9].id | https://openalex.org/keywords/boolean-network |
| keywords[9].score | 0.4391269385814667 |
| keywords[9].display_name | Boolean network |
| keywords[10].id | https://openalex.org/keywords/boolean-expression |
| keywords[10].score | 0.43886905908584595 |
| keywords[10].display_name | Boolean expression |
| keywords[11].id | https://openalex.org/keywords/combinatorics |
| keywords[11].score | 0.4154568910598755 |
| keywords[11].display_name | Combinatorics |
| keywords[12].id | https://openalex.org/keywords/clique |
| keywords[12].score | 0.41389793157577515 |
| keywords[12].display_name | Clique |
| keywords[13].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[13].score | 0.3938550651073456 |
| keywords[13].display_name | Theoretical computer science |
| keywords[14].id | https://openalex.org/keywords/computer-science |
| keywords[14].score | 0.3331069350242615 |
| keywords[14].display_name | Computer science |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2309.15026 |
| 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/2309.15026 |
| 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/2309.15026 |
| locations[1].id | doi:10.48550/arxiv.2309.15026 |
| 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.2309.15026 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5056991051 |
| authorships[0].author.orcid | https://orcid.org/0000-0002-0194-9360 |
| authorships[0].author.display_name | Hsiang-Hsuan Liu |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Liu, Alison Hsiang-Hsuan |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5027137684 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-9520-7340 |
| authorships[1].author.display_name | Nikhil S. Mande |
| authorships[1].author_position | last |
| authorships[1].raw_author_name | Mande, Nikhil S. |
| 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/2309.15026 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | Instance complexity of Boolean functions |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T12072 |
| primary_topic.field.id | https://openalex.org/fields/17 |
| primary_topic.field.display_name | Computer Science |
| primary_topic.score | 0.9958999752998352 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/1702 |
| primary_topic.subfield.display_name | Artificial Intelligence |
| primary_topic.display_name | Machine Learning and Algorithms |
| related_works | https://openalex.org/W2735569833, https://openalex.org/W155681467, https://openalex.org/W2106622045, https://openalex.org/W3204916073, https://openalex.org/W2495817859, https://openalex.org/W2234833091, https://openalex.org/W4388918472, https://openalex.org/W4231391991, https://openalex.org/W4239032960, https://openalex.org/W1481719945 |
| cited_by_count | 0 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2309.15026 |
| 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/2309.15026 |
| 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/2309.15026 |
| primary_location.id | pmh:oai:arXiv.org:2309.15026 |
| 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/2309.15026 |
| 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/2309.15026 |
| publication_date | 2023-09-26 |
| publication_year | 2023 |
| referenced_works_count | 0 |
| abstract_inverted_index.1 | 121, 165 |
| abstract_inverted_index.a | 46, 152, 221, 238, 242, 284 |
| abstract_inverted_index.As | 151 |
| abstract_inverted_index.In | 0, 188 |
| abstract_inverted_index.It | 219 |
| abstract_inverted_index.We | 132, 173, 236, 257 |
| abstract_inverted_index.an | 16, 28, 70, 82 |
| abstract_inverted_index.be | 209 |
| abstract_inverted_index.by | 25, 31, 141, 199, 246 |
| abstract_inverted_index.et | 108, 139, 201 |
| abstract_inverted_index.if | 226 |
| abstract_inverted_index.in | 38, 77, 241, 265 |
| abstract_inverted_index.is | 18, 84, 220, 228, 263, 283 |
| abstract_inverted_index.it | 26, 104 |
| abstract_inverted_index.of | 3, 6, 15, 22, 60, 63, 69, 81, 137, 147, 179, 212, 251, 271 |
| abstract_inverted_index.on | 27, 127 |
| abstract_inverted_index.or | 129 |
| abstract_inverted_index.to | 208, 215, 224 |
| abstract_inverted_index.we | 44, 154, 193, 275 |
| abstract_inverted_index.The | 79 |
| abstract_inverted_index.al. | 109, 140 |
| abstract_inverted_index.all | 89, 189, 233 |
| abstract_inverted_index.and | 66, 93, 102, 170, 185, 196, 254 |
| abstract_inverted_index.are | 122, 166 |
| abstract_inverted_index.ask | 225 |
| abstract_inverted_index.for | 50, 53, 99, 232, 269, 278 |
| abstract_inverted_index.its | 85, 171 |
| abstract_inverted_index.one | 128 |
| abstract_inverted_index.out | 207 |
| abstract_inverted_index.the | 1, 9, 19, 32, 41, 58, 61, 64, 67, 75, 134, 144, 157, 167, 176, 190, 203, 210, 229, 248, 252, 260, 266, 280 |
| abstract_inverted_index.two | 130 |
| abstract_inverted_index.Naor | 94 |
| abstract_inverted_index.al., | 202 |
| abstract_inverted_index.also | 174 |
| abstract_inverted_index.area | 2 |
| abstract_inverted_index.both | 270 |
| abstract_inverted_index.cost | 13, 35, 48, 62, 68, 80, 87 |
| abstract_inverted_index.like | 183 |
| abstract_inverted_index.made | 24 |
| abstract_inverted_index.most | 10, 33 |
| abstract_inverted_index.only | 158 |
| abstract_inverted_index.over | 88 |
| abstract_inverted_index.show | 237, 258 |
| abstract_inverted_index.size | 268 |
| abstract_inverted_index.some | 180 |
| abstract_inverted_index.that | 56, 73, 114, 125, 156, 259 |
| abstract_inverted_index.this | 97, 227 |
| abstract_inverted_index.very | 243 |
| abstract_inverted_index.with | 118, 162 |
| abstract_inverted_index.among | 111 |
| abstract_inverted_index.bound | 231 |
| abstract_inverted_index.graph | 181 |
| abstract_inverted_index.input | 76, 267 |
| abstract_inverted_index.knows | 74 |
| abstract_inverted_index.other | 112 |
| abstract_inverted_index.query | 4, 51, 213 |
| abstract_inverted_index.ratio | 59, 211, 262 |
| abstract_inverted_index.study | 175, 194 |
| abstract_inverted_index.these | 272 |
| abstract_inverted_index.those | 124, 197 |
| abstract_inverted_index.turns | 206 |
| abstract_inverted_index.which | 279 |
| abstract_inverted_index.while | 274 |
| abstract_inverted_index.Parity | 168 |
| abstract_inverted_index.above, | 195 |
| abstract_inverted_index.answer | 240 |
| abstract_inverted_index.depend | 126 |
| abstract_inverted_index.dubbed | 103 |
| abstract_inverted_index.input. | 29 |
| abstract_inverted_index.linear | 264 |
| abstract_inverted_index.number | 21 |
| abstract_inverted_index.online | 39 |
| abstract_inverted_index.ratio, | 43 |
| abstract_inverted_index.result | 136 |
| abstract_inverted_index.sense, | 245 |
| abstract_inverted_index.strong | 244 |
| abstract_inverted_index.widely | 11 |
| abstract_inverted_index.Boolean | 7, 54, 100, 116, 149, 160, 191, 234 |
| abstract_inverted_index.correct | 230 |
| abstract_inverted_index.exhibit | 276 |
| abstract_inverted_index.inputs. | 90 |
| abstract_inverted_index.largest | 86 |
| abstract_inverted_index.measure | 14, 36, 49, 98 |
| abstract_inverted_index.minimum | 216 |
| abstract_inverted_index.natural | 34, 222 |
| abstract_inverted_index.optimal | 71 |
| abstract_inverted_index.queries | 23 |
| abstract_inverted_index.showed, | 110 |
| abstract_inverted_index.studied | 12, 37, 198 |
| abstract_inverted_index.Grossman | 107, 138, 200 |
| abstract_inverted_index.advance. | 78 |
| abstract_inverted_index.captures | 57 |
| abstract_inverted_index.conclude | 155 |
| abstract_inverted_index.consider | 45 |
| abstract_inverted_index.function | 169 |
| abstract_inverted_index.instance | 105, 119, 145, 163, 177, 204, 249, 281 |
| abstract_inverted_index.k-clique | 186 |
| abstract_inverted_index.monotone | 115 |
| abstract_inverted_index.negative | 239 |
| abstract_inverted_index.question | 223 |
| abstract_inverted_index.results, | 113 |
| abstract_inverted_index.Grossman, | 91 |
| abstract_inverted_index.Motivated | 30 |
| abstract_inverted_index.[ITCS'20] | 95 |
| abstract_inverted_index.algorithm | 17, 65, 72, 83 |
| abstract_inverted_index.analyzing | 247 |
| abstract_inverted_index.constant. | 285 |
| abstract_inverted_index.corollary | 153 |
| abstract_inverted_index.different | 47 |
| abstract_inverted_index.functions | 55, 117, 161, 192 |
| abstract_inverted_index.precisely | 123 |
| abstract_inverted_index.symmetric | 148, 159 |
| abstract_inverted_index.algorithms | 52, 277 |
| abstract_inverted_index.complement | 133 |
| abstract_inverted_index.completely | 142 |
| abstract_inverted_index.complexity | 5, 120, 146, 164, 178, 205, 214, 250, 282 |
| abstract_inverted_index.functions, | 8, 101, 273 |
| abstract_inverted_index.functions. | 150, 235, 256 |
| abstract_inverted_index.introduced | 96 |
| abstract_inverted_index.properties | 182 |
| abstract_inverted_index.variables. | 131 |
| abstract_inverted_index.worst-case | 20 |
| abstract_inverted_index.Komargodski | 92 |
| abstract_inverted_index.Odd-Max-Bit | 255 |
| abstract_inverted_index.algorithms, | 40 |
| abstract_inverted_index.certificate | 217 |
| abstract_inverted_index.competitive | 42 |
| abstract_inverted_index.complement. | 172 |
| abstract_inverted_index.complexity. | 106, 218 |
| abstract_inverted_index.Connectivity | 184 |
| abstract_inverted_index.Greater-Than | 253 |
| abstract_inverted_index.containment. | 187 |
| abstract_inverted_index.characterizing | 143 |
| abstract_inverted_index.above-mentioned | 135, 261 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 2 |
| citation_normalized_percentile |