Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR14-037 | 21st March 2014 20:17

Succinct and explicit circuits for sorting and connectivity

RSS-Feed




TR14-037
Authors: Hamidreza Jahanjou, Eric Miles, Emanuele Viola
Publication: 21st March 2014 20:17
Downloads: 1118
Keywords: 


Abstract:

We study which functions can be computed by efficient circuits whose gate connections are very easy to compute. We give quasilinear-size circuits for sorting whose connections can be computed by decision trees with depth logarithmic in the length of the gate description. We also show that NL has NC$^2$ circuits whose connections can be computed with constant locality.



ISSN 1433-8092 | Imprint