Paper Info
Title
On Some Recent Projection Switching Lemmas for Small Depth Circuits.
Abstract
Switching Lemmas are an important technique for analyzing and proving lower bounds for constant-depth Boolean circuits. Typically, in applying a switching lemma, we restrict the circuit under consideration by setting a few of the input variables to constants at random while leaving the other variables unset. A Switching lemma guarantees, roughly, that any small Boolean circuit simplifies considerably under such a restriction. Recently, researchers have analyzed what happens to constant-depth circuits under random projections, where in addition to the above, we also identify some variables with each other. This analysis has yielded strong Projection Switching Lemmas, which have been used to prove some new results in Boolean circuit complexity, including the resolution of some long standing open problems in the area. We review some of these projection switching lemmas and their applications.
Year
Venue
Field
2017
BULLETIN OF THE EUROPEAN ASSOCIATION FOR THEORETICAL COMPUTER SCIENCE
Discrete mathematics,Boolean circuit,Electronic circuit,Mathematics,restrict,Lemma (mathematics)
DocType
Volume
Issue
Journal
122
122
ISSN
Citations 
PageRank 
0252-9742
0
0.34
References 
Authors
0
1
Name
Order
Citations
PageRank
Srikanth Srinivasan113221.31