All Questions

Filter by
Sorted by
Tagged with
16
votes
2answers
314 views

On the status of learnability inside $\mathsf{TC}^0$

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\...
3
votes
2answers
534 views

Boolean Circuit in a Black Box?

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here. Let's equip a normal Turing machine with a "black box ...
0
votes
1answer
201 views

Bent and hyper-bent functions

Is the AND logic function considered to be a bent function? If it is, how could one make a hyper-bent funtion using logic gates? Thank you (two questions in one: very efficient :) )