April 23, 2014

Workshop: Analysis and Geometry of Boolean Threshold Functions – Oct 21-22, 2010

Organizers: Ryan O'Donnell and Rocco Servedio

Linear Threshold Functions (LTFs) are boolean functions f : {0,1}^n -> {-1,1} expressible as f(x) = sign(c_0 + c_1 x_1 + … + c_n x_n). Polynomial Threshold Functions (PTFs) are the low-degree generalization. LTFs and PTFs play an important role in circuit complexity, learning theory, Boolean function theory, social choice, quantum complexity and other areas.

Exciting advances have recently been made in our understanding of LTFs and PTFs and their relation to topics such as property testing, approximation, derandomization, learning, and more.  The workshop, organized by the Center for Computational Intractability,  will bring together researchers interested in this recent progress and in associated analytic, probabilistic, and geometric topics and techniques, such as derandomization, invariance principles, regularity lemmas, Gaussian geometry, noise sensitivity and anti-concentration.

Schedule and Abstracts

All talks will be held in the main meeting room (Prince William ballroom) at the Nassau Inn. The workshop dinner will be at the Palmer House. See this map for directions.

Lodging: If you plan to come to the workshop and need a hotel room, we suggest you register (using the registration form at the bottom of this page) and reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728  and you should ask for group number 14766 or `Analysis & Geometry workshop' to get the special workshop rate. The cutoff date for the special rate is Sep 17 2010. DO NOT BOOK YOUR ROOM ONLINE! THE SPECIAL RATE IS ONLY AVAILABLE WHEN MAKING A RESERVATION BY PHONE.

Registration: Please use the form at the bottom of this page to register to the workshop. (Last minute registration is ok but please do not register on the last business day prior to the workshop).

Financial support: We have some limited funds to cover expenses of students attending the workshop. If you need such support please fill in the support request form at the bottom of this page. Once the workshop is over, you will also need to fill the following form: pu-expense-report. Guidelines for filling the expense report are available here. If you are being reimbursed by PU  please read the following airfare guidelines carefully. All flights must be booked with a US flagship carrier airlines in order to receive reimbursement for the expense. Ask your travel agent or airline customer service representative if your flight will qualify if in doubt.

Important: If the travel includes stops in addition to the workshop location, appropriate documentation including the fare comparison direct to/from the conference location at the time of purchase must be included with the request for reimbursement. Documentation/comparisons cannot be dated  after the trip dates.

The Center for Computational Intractability especially encourages the participation in our workshops of researchers from backgrounds that are  traditionally underrepresented within the computer science research community.


Questions regarding the scientific program should be directed to ltf.ptf.workshop .

For questions regarding local arrangements contact ltf.ptf.local

Registration is now closed. You can still register at the workshop itself.