DeepSAT: An EDA-Driven Learning Framework for SAT Article Swipe
Min Li
,
Zhengyuan Shi
,
Qiuxia Lai
,
Sadaf Khan
,
Qiang Xu
·
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2205.13745
YOU?
·
· 2022
· Open Access
·
· DOI: https://doi.org/10.48550/arxiv.2205.13745
We present DeepSAT, a novel end-to-end learning framework for the Boolean satisfiability (SAT) problem. Unlike existing solutions trained on random SAT instances with relatively weak supervision, we propose applying the knowledge of the well-developed electronic design automation (EDA) field for SAT solving. Specifically, we first resort to logic synthesis algorithms to pre-process SAT instances into optimized and-inverter graphs (AIGs). By doing so, the distribution diversity among various SAT instances can be dramatically reduced, which facilitates improving the generalization capability of the learned model. Next, we regard the distribution of SAT solutions being a product of conditional Bernoulli distributions. Based on this observation, we approximate the SAT solving procedure with a conditional generative model, leveraging a novel directed acyclic graph neural network (DAGNN) with two polarity prototypes for conditional SAT modeling. To effectively train the generative model, with the help of logic simulation tools, we obtain the probabilities of nodes in the AIG being logic `1' as rich supervision. We conduct comprehensive experiments on various SAT problems. Our results show that, DeepSAT achieves significant accuracy improvements over state-of-the-art learning-based SAT solutions, especially when generalized to SAT instances that are relatively large or with diverse distributions.
Related Topics
Concepts
Metadata
- Type
- preprint
- Language
- en
- Landing Page
- http://arxiv.org/abs/2205.13745
- https://arxiv.org/pdf/2205.13745
- OA Status
- green
- Cited By
- 3
- Related Works
- 10
- OpenAlex ID
- https://openalex.org/W4281835466
All OpenAlex metadata
Raw OpenAlex JSON
- OpenAlex ID
-
https://openalex.org/W4281835466Canonical identifier for this work in OpenAlex
- DOI
-
https://doi.org/10.48550/arxiv.2205.13745Digital Object Identifier
- Title
-
DeepSAT: An EDA-Driven Learning Framework for SATWork title
- Type
-
preprintOpenAlex work type
- Language
-
enPrimary language
- Publication year
-
2022Year of publication
- Publication date
-
2022-05-27Full publication date if available
- Authors
-
Min Li, Zhengyuan Shi, Qiuxia Lai, Sadaf Khan, Qiang XuList of authors in order
- Landing page
-
https://arxiv.org/abs/2205.13745Publisher landing page
- PDF URL
-
https://arxiv.org/pdf/2205.13745Direct 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/2205.13745Direct OA link when available
- Concepts
-
Boolean satisfiability problem, Computer science, Theoretical computer science, Generalization, Satisfiability, Boolean function, Artificial intelligence, Machine learning, Algorithm, Mathematics, Mathematical analysisTop concepts (fields/topics) attached by OpenAlex
- Cited by
-
3Total citation count in OpenAlex
- Citations by year (recent)
-
2024: 1, 2023: 2Per-year citation counts (last 5 years)
- Related works (count)
-
10Other works algorithmically related by OpenAlex
Full payload
| id | https://openalex.org/W4281835466 |
|---|---|
| doi | https://doi.org/10.48550/arxiv.2205.13745 |
| ids.doi | https://doi.org/10.48550/arxiv.2205.13745 |
| ids.openalex | https://openalex.org/W4281835466 |
| fwci | |
| type | preprint |
| title | DeepSAT: An EDA-Driven Learning Framework for SAT |
| biblio.issue | |
| biblio.volume | |
| biblio.last_page | |
| biblio.first_page | |
| topics[0].id | https://openalex.org/T11948 |
| topics[0].field.id | https://openalex.org/fields/25 |
| topics[0].field.display_name | Materials Science |
| topics[0].score | 0.9922000169754028 |
| topics[0].domain.id | https://openalex.org/domains/3 |
| topics[0].domain.display_name | Physical Sciences |
| topics[0].subfield.id | https://openalex.org/subfields/2505 |
| topics[0].subfield.display_name | Materials Chemistry |
| topics[0].display_name | Machine Learning in Materials Science |
| topics[1].id | https://openalex.org/T10260 |
| topics[1].field.id | https://openalex.org/fields/17 |
| topics[1].field.display_name | Computer Science |
| topics[1].score | 0.9589999914169312 |
| topics[1].domain.id | https://openalex.org/domains/3 |
| topics[1].domain.display_name | Physical Sciences |
| topics[1].subfield.id | https://openalex.org/subfields/1710 |
| topics[1].subfield.display_name | Information Systems |
| topics[1].display_name | Software Engineering Research |
| topics[2].id | https://openalex.org/T10142 |
| topics[2].field.id | https://openalex.org/fields/17 |
| topics[2].field.display_name | Computer Science |
| topics[2].score | 0.9580000042915344 |
| topics[2].domain.id | https://openalex.org/domains/3 |
| topics[2].domain.display_name | Physical Sciences |
| topics[2].subfield.id | https://openalex.org/subfields/1703 |
| topics[2].subfield.display_name | Computational Theory and Mathematics |
| topics[2].display_name | Formal Methods in Verification |
| is_xpac | False |
| apc_list | |
| apc_paid | |
| concepts[0].id | https://openalex.org/C6943359 |
| concepts[0].level | 2 |
| concepts[0].score | 0.6713156700134277 |
| concepts[0].wikidata | https://www.wikidata.org/wiki/Q875276 |
| concepts[0].display_name | Boolean satisfiability problem |
| concepts[1].id | https://openalex.org/C41008148 |
| concepts[1].level | 0 |
| concepts[1].score | 0.6676815748214722 |
| concepts[1].wikidata | https://www.wikidata.org/wiki/Q21198 |
| concepts[1].display_name | Computer science |
| concepts[2].id | https://openalex.org/C80444323 |
| concepts[2].level | 1 |
| concepts[2].score | 0.5289832353591919 |
| concepts[2].wikidata | https://www.wikidata.org/wiki/Q2878974 |
| concepts[2].display_name | Theoretical computer science |
| concepts[3].id | https://openalex.org/C177148314 |
| concepts[3].level | 2 |
| concepts[3].score | 0.5168319344520569 |
| concepts[3].wikidata | https://www.wikidata.org/wiki/Q170084 |
| concepts[3].display_name | Generalization |
| concepts[4].id | https://openalex.org/C168773769 |
| concepts[4].level | 2 |
| concepts[4].score | 0.49322789907455444 |
| concepts[4].wikidata | https://www.wikidata.org/wiki/Q1350299 |
| concepts[4].display_name | Satisfiability |
| concepts[5].id | https://openalex.org/C187455244 |
| concepts[5].level | 2 |
| concepts[5].score | 0.4300510287284851 |
| concepts[5].wikidata | https://www.wikidata.org/wiki/Q942353 |
| concepts[5].display_name | Boolean function |
| concepts[6].id | https://openalex.org/C154945302 |
| concepts[6].level | 1 |
| concepts[6].score | 0.39055415987968445 |
| concepts[6].wikidata | https://www.wikidata.org/wiki/Q11660 |
| concepts[6].display_name | Artificial intelligence |
| concepts[7].id | https://openalex.org/C119857082 |
| concepts[7].level | 1 |
| concepts[7].score | 0.3489484190940857 |
| concepts[7].wikidata | https://www.wikidata.org/wiki/Q2539 |
| concepts[7].display_name | Machine learning |
| concepts[8].id | https://openalex.org/C11413529 |
| concepts[8].level | 1 |
| concepts[8].score | 0.33325716853141785 |
| concepts[8].wikidata | https://www.wikidata.org/wiki/Q8366 |
| concepts[8].display_name | Algorithm |
| concepts[9].id | https://openalex.org/C33923547 |
| concepts[9].level | 0 |
| concepts[9].score | 0.19294962286949158 |
| concepts[9].wikidata | https://www.wikidata.org/wiki/Q395 |
| concepts[9].display_name | Mathematics |
| concepts[10].id | https://openalex.org/C134306372 |
| concepts[10].level | 1 |
| concepts[10].score | 0.0 |
| concepts[10].wikidata | https://www.wikidata.org/wiki/Q7754 |
| concepts[10].display_name | Mathematical analysis |
| keywords[0].id | https://openalex.org/keywords/boolean-satisfiability-problem |
| keywords[0].score | 0.6713156700134277 |
| keywords[0].display_name | Boolean satisfiability problem |
| keywords[1].id | https://openalex.org/keywords/computer-science |
| keywords[1].score | 0.6676815748214722 |
| keywords[1].display_name | Computer science |
| keywords[2].id | https://openalex.org/keywords/theoretical-computer-science |
| keywords[2].score | 0.5289832353591919 |
| keywords[2].display_name | Theoretical computer science |
| keywords[3].id | https://openalex.org/keywords/generalization |
| keywords[3].score | 0.5168319344520569 |
| keywords[3].display_name | Generalization |
| keywords[4].id | https://openalex.org/keywords/satisfiability |
| keywords[4].score | 0.49322789907455444 |
| keywords[4].display_name | Satisfiability |
| keywords[5].id | https://openalex.org/keywords/boolean-function |
| keywords[5].score | 0.4300510287284851 |
| keywords[5].display_name | Boolean function |
| keywords[6].id | https://openalex.org/keywords/artificial-intelligence |
| keywords[6].score | 0.39055415987968445 |
| keywords[6].display_name | Artificial intelligence |
| keywords[7].id | https://openalex.org/keywords/machine-learning |
| keywords[7].score | 0.3489484190940857 |
| keywords[7].display_name | Machine learning |
| keywords[8].id | https://openalex.org/keywords/algorithm |
| keywords[8].score | 0.33325716853141785 |
| keywords[8].display_name | Algorithm |
| keywords[9].id | https://openalex.org/keywords/mathematics |
| keywords[9].score | 0.19294962286949158 |
| keywords[9].display_name | Mathematics |
| language | en |
| locations[0].id | pmh:oai:arXiv.org:2205.13745 |
| 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/2205.13745 |
| locations[0].version | submittedVersion |
| locations[0].raw_type | |
| 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/2205.13745 |
| locations[1].id | doi:10.48550/arxiv.2205.13745 |
| 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.2205.13745 |
| indexed_in | arxiv, datacite |
| authorships[0].author.id | https://openalex.org/A5100400706 |
| authorships[0].author.orcid | https://orcid.org/0000-0001-7958-6670 |
| authorships[0].author.display_name | Min Li |
| authorships[0].author_position | first |
| authorships[0].raw_author_name | Li, Min |
| authorships[0].is_corresponding | False |
| authorships[1].author.id | https://openalex.org/A5091583458 |
| authorships[1].author.orcid | https://orcid.org/0000-0002-2186-9579 |
| authorships[1].author.display_name | Zhengyuan Shi |
| authorships[1].author_position | middle |
| authorships[1].raw_author_name | Shi, Zhengyuan |
| authorships[1].is_corresponding | False |
| authorships[2].author.id | https://openalex.org/A5059830795 |
| authorships[2].author.orcid | https://orcid.org/0000-0001-6872-5540 |
| authorships[2].author.display_name | Qiuxia Lai |
| authorships[2].author_position | middle |
| authorships[2].raw_author_name | Lai, Qiuxia |
| authorships[2].is_corresponding | False |
| authorships[3].author.id | https://openalex.org/A5039005141 |
| authorships[3].author.orcid | https://orcid.org/0000-0002-2150-7535 |
| authorships[3].author.display_name | Sadaf Khan |
| authorships[3].author_position | middle |
| authorships[3].raw_author_name | Khan, Sadaf |
| authorships[3].is_corresponding | False |
| authorships[4].author.id | https://openalex.org/A5088556682 |
| authorships[4].author.orcid | https://orcid.org/0000-0001-6747-126X |
| authorships[4].author.display_name | Qiang Xu |
| authorships[4].author_position | last |
| authorships[4].raw_author_name | Xu, Qiang |
| authorships[4].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/2205.13745 |
| open_access.oa_status | green |
| open_access.any_repository_has_fulltext | False |
| created_date | 2025-10-10T00:00:00 |
| display_name | DeepSAT: An EDA-Driven Learning Framework for SAT |
| has_fulltext | False |
| is_retracted | False |
| updated_date | 2025-11-06T06:51:31.235846 |
| primary_topic.id | https://openalex.org/T11948 |
| primary_topic.field.id | https://openalex.org/fields/25 |
| primary_topic.field.display_name | Materials Science |
| primary_topic.score | 0.9922000169754028 |
| primary_topic.domain.id | https://openalex.org/domains/3 |
| primary_topic.domain.display_name | Physical Sciences |
| primary_topic.subfield.id | https://openalex.org/subfields/2505 |
| primary_topic.subfield.display_name | Materials Chemistry |
| primary_topic.display_name | Machine Learning in Materials Science |
| related_works | https://openalex.org/W3176904788, https://openalex.org/W21597398, https://openalex.org/W4298153058, https://openalex.org/W2408080066, https://openalex.org/W2268872489, https://openalex.org/W1913543287, https://openalex.org/W2014111643, https://openalex.org/W2963044240, https://openalex.org/W2076399409, https://openalex.org/W2102364390 |
| cited_by_count | 3 |
| 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 | 2 |
| locations_count | 2 |
| best_oa_location.id | pmh:oai:arXiv.org:2205.13745 |
| 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/2205.13745 |
| best_oa_location.version | submittedVersion |
| best_oa_location.raw_type | |
| 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/2205.13745 |
| primary_location.id | pmh:oai:arXiv.org:2205.13745 |
| 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/2205.13745 |
| primary_location.version | submittedVersion |
| primary_location.raw_type | |
| 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/2205.13745 |
| publication_date | 2022-05-27 |
| publication_year | 2022 |
| referenced_works_count | 0 |
| abstract_inverted_index.a | 3, 92, 109, 114 |
| abstract_inverted_index.By | 59 |
| abstract_inverted_index.To | 130 |
| abstract_inverted_index.We | 0, 158 |
| abstract_inverted_index.as | 155 |
| abstract_inverted_index.be | 70 |
| abstract_inverted_index.in | 149 |
| abstract_inverted_index.of | 31, 79, 88, 94, 139, 147 |
| abstract_inverted_index.on | 18, 99, 162 |
| abstract_inverted_index.or | 190 |
| abstract_inverted_index.to | 46, 50, 183 |
| abstract_inverted_index.we | 26, 43, 84, 102, 143 |
| abstract_inverted_index.AIG | 151 |
| abstract_inverted_index.Our | 166 |
| abstract_inverted_index.SAT | 20, 40, 52, 67, 89, 105, 128, 164, 178, 184 |
| abstract_inverted_index.`1' | 154 |
| abstract_inverted_index.are | 187 |
| abstract_inverted_index.can | 69 |
| abstract_inverted_index.for | 8, 39, 126 |
| abstract_inverted_index.so, | 61 |
| abstract_inverted_index.the | 9, 29, 32, 62, 76, 80, 86, 104, 133, 137, 145, 150 |
| abstract_inverted_index.two | 123 |
| abstract_inverted_index.help | 138 |
| abstract_inverted_index.into | 54 |
| abstract_inverted_index.over | 175 |
| abstract_inverted_index.rich | 156 |
| abstract_inverted_index.show | 168 |
| abstract_inverted_index.that | 186 |
| abstract_inverted_index.this | 100 |
| abstract_inverted_index.weak | 24 |
| abstract_inverted_index.when | 181 |
| abstract_inverted_index.with | 22, 108, 122, 136, 191 |
| abstract_inverted_index.(EDA) | 37 |
| abstract_inverted_index.(SAT) | 12 |
| abstract_inverted_index.Based | 98 |
| abstract_inverted_index.Next, | 83 |
| abstract_inverted_index.among | 65 |
| abstract_inverted_index.being | 91, 152 |
| abstract_inverted_index.doing | 60 |
| abstract_inverted_index.field | 38 |
| abstract_inverted_index.first | 44 |
| abstract_inverted_index.graph | 118 |
| abstract_inverted_index.large | 189 |
| abstract_inverted_index.logic | 47, 140, 153 |
| abstract_inverted_index.nodes | 148 |
| abstract_inverted_index.novel | 4, 115 |
| abstract_inverted_index.that, | 169 |
| abstract_inverted_index.train | 132 |
| abstract_inverted_index.which | 73 |
| abstract_inverted_index.Unlike | 14 |
| abstract_inverted_index.design | 35 |
| abstract_inverted_index.graphs | 57 |
| abstract_inverted_index.model, | 112, 135 |
| abstract_inverted_index.model. | 82 |
| abstract_inverted_index.neural | 119 |
| abstract_inverted_index.obtain | 144 |
| abstract_inverted_index.random | 19 |
| abstract_inverted_index.regard | 85 |
| abstract_inverted_index.resort | 45 |
| abstract_inverted_index.tools, | 142 |
| abstract_inverted_index.(AIGs). | 58 |
| abstract_inverted_index.(DAGNN) | 121 |
| abstract_inverted_index.Boolean | 10 |
| abstract_inverted_index.DeepSAT | 170 |
| abstract_inverted_index.acyclic | 117 |
| abstract_inverted_index.conduct | 159 |
| abstract_inverted_index.diverse | 192 |
| abstract_inverted_index.learned | 81 |
| abstract_inverted_index.network | 120 |
| abstract_inverted_index.present | 1 |
| abstract_inverted_index.product | 93 |
| abstract_inverted_index.propose | 27 |
| abstract_inverted_index.results | 167 |
| abstract_inverted_index.solving | 106 |
| abstract_inverted_index.trained | 17 |
| abstract_inverted_index.various | 66, 163 |
| abstract_inverted_index.DeepSAT, | 2 |
| abstract_inverted_index.accuracy | 173 |
| abstract_inverted_index.achieves | 171 |
| abstract_inverted_index.applying | 28 |
| abstract_inverted_index.directed | 116 |
| abstract_inverted_index.existing | 15 |
| abstract_inverted_index.learning | 6 |
| abstract_inverted_index.polarity | 124 |
| abstract_inverted_index.problem. | 13 |
| abstract_inverted_index.reduced, | 72 |
| abstract_inverted_index.solving. | 41 |
| abstract_inverted_index.Bernoulli | 96 |
| abstract_inverted_index.diversity | 64 |
| abstract_inverted_index.framework | 7 |
| abstract_inverted_index.improving | 75 |
| abstract_inverted_index.instances | 21, 53, 68, 185 |
| abstract_inverted_index.knowledge | 30 |
| abstract_inverted_index.modeling. | 129 |
| abstract_inverted_index.optimized | 55 |
| abstract_inverted_index.problems. | 165 |
| abstract_inverted_index.procedure | 107 |
| abstract_inverted_index.solutions | 16, 90 |
| abstract_inverted_index.synthesis | 48 |
| abstract_inverted_index.algorithms | 49 |
| abstract_inverted_index.automation | 36 |
| abstract_inverted_index.capability | 78 |
| abstract_inverted_index.electronic | 34 |
| abstract_inverted_index.end-to-end | 5 |
| abstract_inverted_index.especially | 180 |
| abstract_inverted_index.generative | 111, 134 |
| abstract_inverted_index.leveraging | 113 |
| abstract_inverted_index.prototypes | 125 |
| abstract_inverted_index.relatively | 23, 188 |
| abstract_inverted_index.simulation | 141 |
| abstract_inverted_index.solutions, | 179 |
| abstract_inverted_index.approximate | 103 |
| abstract_inverted_index.conditional | 95, 110, 127 |
| abstract_inverted_index.effectively | 131 |
| abstract_inverted_index.experiments | 161 |
| abstract_inverted_index.facilitates | 74 |
| abstract_inverted_index.generalized | 182 |
| abstract_inverted_index.pre-process | 51 |
| abstract_inverted_index.significant | 172 |
| abstract_inverted_index.and-inverter | 56 |
| abstract_inverted_index.distribution | 63, 87 |
| abstract_inverted_index.dramatically | 71 |
| abstract_inverted_index.improvements | 174 |
| abstract_inverted_index.observation, | 101 |
| abstract_inverted_index.supervision, | 25 |
| abstract_inverted_index.supervision. | 157 |
| abstract_inverted_index.Specifically, | 42 |
| abstract_inverted_index.comprehensive | 160 |
| abstract_inverted_index.probabilities | 146 |
| abstract_inverted_index.distributions. | 97, 193 |
| abstract_inverted_index.generalization | 77 |
| abstract_inverted_index.learning-based | 177 |
| abstract_inverted_index.satisfiability | 11 |
| abstract_inverted_index.well-developed | 33 |
| abstract_inverted_index.state-of-the-art | 176 |
| cited_by_percentile_year | |
| countries_distinct_count | 0 |
| institutions_distinct_count | 5 |
| citation_normalized_percentile |