TY - GEN
T1 - Symmetric functions capture general functions (Extended abstract)
AU - Lipton, Richard J.
AU - Regan, Kenneth W.
AU - Rudra, Atri
PY - 2011
Y1 - 2011
N2 - 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 f sym such that f can be computed from f sym and vice-versa (modulo an extra deterministic linear time computation). For f over finite fields, f sym is (necessarily) over an extension field. This reduction is optimal in size of the extension field. For polynomial functions, the degree of f sym is not optimal. We present another reduction that has optimal degree "blowup" but is worse in the other parameters.
AB - 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 f sym such that f can be computed from f sym and vice-versa (modulo an extra deterministic linear time computation). For f over finite fields, f sym is (necessarily) over an extension field. This reduction is optimal in size of the extension field. For polynomial functions, the degree of f sym is not optimal. We present another reduction that has optimal degree "blowup" but is worse in the other parameters.
UR - https://www.scopus.com/pages/publications/80052104656
U2 - 10.1007/978-3-642-22993-0_40
DO - 10.1007/978-3-642-22993-0_40
M3 - Conference contribution
AN - SCOPUS:80052104656
SN - 9783642229923
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 436
EP - 447
BT - Mathematical Foundations of Computer Science 2011 - 36th International Symposium, MFCS 2011, Proceedings
T2 - 36th International Symposium on Mathematical Foundations of Computer Science, MFCS 2011
Y2 - 22 August 2011 through 26 August 2011
ER -