COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Combinatorics Seminar > Establishing Complexity of Problems Parameterized Above Average

## Establishing Complexity of Problems Parameterized Above AverageAdd to your list(s) Download to your calendar using vCal - Gregory Gutin (Royal Holloway, University of London)
- Thursday 04 February 2010, 14:30-15:30
- MR12.
If you have a question about this talk, please contact Andrew Thomason. In the Max Acyclic Subdigraph problem we are given a digraph D and ask
whether D contains an acyclic subdigraph with at least k arcs. The
problem is NP-complete and it is easy to see that the problem is
fixed-parameter tractable, i.e., there is an algorithm of running time
f(k)n Mahajan, Raman and Sikdar (2006, 2009), and by Benny Chor (prior to 2006) asked whether this and other problems parameterized above the average are fixed-parameter tractable (the problems include Max r-SAT, Betweenness, and Max Lin). Most of there problems have been recently shown to be fixed-parameter tractable. Methods involved in proving these results include probabilistic
inequalities, harmonic analysis of real-valued
functions with boolean domain, linear algebra, and
algorithmic-combinatorial arguments.
Some new results obtained in this research are of potential interest
for several areas of discrete mathematics and computer science. The
examples include a new variant of the hypercontractive inequality and
an association of Fourier expansions of real-valued functions with
boolean domain with weighted systems of linear equations over F I’ll mention results obtained together with N. Alon, R. Crowston, M. Jones, E.J. Kim, M. Mnich, I.Z. Ruzsa, S. Szeider, and A. Yeo. This talk is part of the Combinatorics Seminar series. ## This talk is included in these lists:- All CMS events
- All Talks (aka the CURE list)
- CMS Events
- Combinatorics Seminar
- DPMMS Lists
- DPMMS Pure Maths Seminar
- DPMMS info aggregator
- DPMMS lists
- MR12
- School of Physical Sciences
- bld31
Note that ex-directory lists are not shown. |
## Other listsReligion, Conflict and its Aftermath BHRU Annual Lecture 2017 Biochem## Other talksTo be confirmed The role of Birkeland currents in the Dungey cycle Surface meltwater ponding and drainage causes ice-shelf flexure Stokes-Smoluchowski-Einstein-Langevin theory for active colloidal suspensions Radiocarbon as a carbon cycle tracer in the 21st century Slaying (or at least taming) a dreadful monster: Louis de Serres' treatise of 1625 for women suffering from infertility |