BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Establishing Complexity of Problems Parameterized Above Average - 
 Gregory Gutin (Royal Holloway\, University of London)
DTSTART:20100204T143000Z
DTEND:20100204T153000Z
UID:TALK22235@talks.cam.ac.uk
CONTACT:Andrew Thomason
DESCRIPTION:In the Max Acyclic Subdigraph problem we are given a digraph D
  and ask\nwhether D contains an acyclic subdigraph with at least k arcs. T
 he\nproblem is NP-complete and it is easy to see that  the problem is\nfix
 ed-parameter tractable\, i.e.\, there is an algorithm of running time\nf(k
 )n^O(1)^ for solving the problem\, where f is a computable function\nof k 
 only and n=|V(D)|. The last result follows from the fact that the\naverage
  number of arcs in an acyclic subdigraph of D is m/2\, where m\nis the num
 ber of arcs in D. Thus\, it is natural to ask another\nquestion: does D ha
 ve an acyclic subdigraph with at least m/2 +k arcs?\n\nMahajan\, Raman and
  Sikdar (2006\, 2009)\, and by Benny Chor (prior to\n2006) asked whether t
 his and other problems parameterized above the\naverage are fixed-paramete
 r tractable (the problems include Max r-SAT\,\nBetweenness\, and Max Lin).
  Most of there problems have been recently\nshown to be fixed-parameter tr
 actable.\n\nMethods involved in proving these results include probabilisti
 c\ninequalities\, harmonic analysis of real-valued\nfunctions with boolean
  domain\, linear algebra\, and\nalgorithmic-combinatorial arguments.\nSome
  new results obtained in this research are of potential interest\nfor seve
 ral areas of discrete mathematics and computer science. The\nexamples incl
 ude a new variant of the hypercontractive inequality and\nan association o
 f Fourier expansions of real-valued functions with\nboolean domain with we
 ighted systems of linear equations over F^n^2.\n\nI'll mention results obt
 ained together with N. Alon\, R. Crowston\, M.\nJones\, E.J. Kim\, M. Mnic
 h\, I.Z. Ruzsa\, S. Szeider\, and A. Yeo.\n
LOCATION:MR12
END:VEVENT
END:VCALENDAR