The Complexity of Finite Functions
Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length < c.n. For any m, if n is sufficiently large, there is a restriction f...
| Main Author: | |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149409 |
| _version_ | 1826193776769499136 |
|---|---|
| author | Vilfan, Bostjan |
| author_facet | Vilfan, Bostjan |
| author_sort | Vilfan, Bostjan |
| collection | MIT |
| description | Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length < c.n. For any m, if n is sufficiently large, there is a restriction f': {0,1,...,d-1}m > {0,...,d-1} of f which, is representable by special class of formulas called homogeneous e-complexes. |
| first_indexed | 2024-09-23T09:44:43Z |
| id | mit-1721.1/149409 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:44:43Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1494092023-03-30T04:08:36Z The Complexity of Finite Functions Vilfan, Bostjan Lower bounds on the length of formulas for finite functions are obtained from a generalization of a theorem of Specker. Let f: (0,1,...,d-1) [0,1,...,d-1] be a function which can be represented by a formula of length < c.n. For any m, if n is sufficiently large, there is a restriction f': {0,1,...,d-1}m > {0,...,d-1} of f which, is representable by special class of formulas called homogeneous e-complexes. 2023-03-29T14:56:21Z 2023-03-29T14:56:21Z 1972-03 https://hdl.handle.net/1721.1/149409 02527958 MIT-LCS-TR-097 MAC-TR-097 application/pdf |
| spellingShingle | Vilfan, Bostjan The Complexity of Finite Functions |
| title | The Complexity of Finite Functions |
| title_full | The Complexity of Finite Functions |
| title_fullStr | The Complexity of Finite Functions |
| title_full_unstemmed | The Complexity of Finite Functions |
| title_short | The Complexity of Finite Functions |
| title_sort | complexity of finite functions |
| url | https://hdl.handle.net/1721.1/149409 |
| work_keys_str_mv | AT vilfanbostjan thecomplexityoffinitefunctions AT vilfanbostjan complexityoffinitefunctions |