STCS Student Seminar

Integer Linear Programs and Local Search for Max-Cut (Author: Svatopluk Poljak)

Speaker: 
Vidya Sagar Sharma, TIFR

Organisers: 

Kumar Saurav

Time: 

Friday, 6 March 2020, 14:00 to 15:00

Venue: 

Abstract: Schaffer and Yannakakis have shown that the max-cut problem with the FLIP neighborhood is polynomial-time local search (PLS) complete, and hence among the most difficult problems in the PLS class.

A Quadratic Lower Bound for Algebraic Branching Programs

Speaker: 
Prerona Chatterjee, TIFR

Organisers: 

Anamay Tengse

Time: 

Friday, 17 January 2020, 16:00 to 17:30

Venue: 

Abstract: An Algebraic Branching Program (ABP) is a layered graph where each edge is labeled by an affine linear form and the first and the last layer have one vertex each, called the “start” and the “end” vertex respectively.

On the Probabilistic Degrees of Symmetric Boolean Functions

Speaker: 

S. Venkitesh

Organisers: 

Vidya Sagar Sharma

Time: 

Friday, 6 December 2019, 14:30 to 15:30

Venue: 

Abstract: The probabilistic degree of a Boolean function f is defined to be the smallest d such that there is a random polynomial P of degree at most d that agrees with f at each point with high probability.

Pages

Subscribe to RSS - STCS Student Seminar