Circuits, Lower Bounds, and Circuit Analysis Algorithms.

我们综述了电路复杂性类、电路下界和电路分析算法之间的联系。电路分析算法包括(其中)可满足性算法、学习算法或自然属性(其是区分在某些特定电路类中可计算的函数和随机函数的算法)。最近的工作表明了这一方向的重要性，通过提供新的有趣的方法来看待旧的结果，例如，关于下限的旧结果，以及通过提供获得新的指导方针(如新的下限或新的学习算法)。最后，我们提出了一些与上述联系和可能的扩展有关的问题。领域：算法、优化和市场

We survey the connections among circuit complexity classes, circuit lower bounds, and circuit analysis algorithms. Circuit analysis algorithms include (among others) satisfiability algorithms, learning algorithms, or natural properties (which are algorithms that discriminate between functions computable in some specific circuit class and random functions). Recent work has indicated the importance of this direction by providing new intriguing ways of looking at old results, like, for example, old results regarding lower bounds, as well as by providing guidelines on acquiring new (like new lower bounds or new learning algorithms). Finally, we pose some problems that pertain to these aforementioned connections and possible extensions on them.Area: Algorithms, Optimizations and Markets