Name
Abstract | ||
|---|---|---|
We show that the set of all functions is equivalent to the set of all symmetric functions (possibly over a larger domain) up to deterministic time complexity. In particular, for any function f, there is an equivalent symmetric function fsym such that f can be computed from fsym and vice-versa (modulo an extra deterministic linear time computation). For f over finite fields, fsym is (necessarily) over an extension field. This reduction is optimal in size of the extension field. For polynomial functions, the degree of fsym is not optimal. We present another reduction that has optimal degree "blowup" but is worse in the other parameters. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/978-3-642-22993-0_40 | MFCS |
Keywords | DocType | Volume |
larger domain,finite field,extension field,extra deterministic linear time,polynomial function,optimal degree,symmetric function,time complexity,general function,equivalent symmetric function fsym | Conference | 6907 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
18 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Richard J. Lipton | 1 | 6412 | 1796.57 |
| Kenneth W. Regan | 2 | 201 | 23.15 |
| Atri Rudra | 3 | 601 | 62.87 |