Research

Writing

Cenny Wenner
Hardness Results for the Shortest Path Problem under Partial Observability
Bachelor thesis, Lund University, Sweden, March 2009
[pdf] Thanks to my supervisor, Thore Husfeldt.

Cenny Wenner
Rule-Based Logical Forms Extraction
NODALIDA 2007 Conference Proceedings, Tartu, Estonia, May 2007, pp. 402-409
[pdf] [poster/pdf] Many thanks to Pierre Nugues.

Current Research Projects

• Hardness of unique games and edge density, integrality gaps, easy and equivalent variants of unique games, methods to derive variants, and inapproximability.
• What is the smallest number of edges a graph can have such that every choice of k vertices cuts at least fk edges?
• Art galleries, to some extent.

Hibernating Research Projects

• Master thesis: Subhash Khot's quasi-random PCPs and Uriel Feige's conjecture on refuting most random 3SAT-instances with cn number of clauses. Relations between average-case and approximation complexity.
• Simplify the proofs of the PCP theorems and applications of PCP theorems. This is a very important problem in our field and I urge you to think about it. Irit Dinur's work seems like a good start. For example, the low-degree test classically demands the proof to encode a lines table that, for each line, encodes the univariate polynomial that is the restriction of the (supposed) proof-polynomial to the line. Instead of storing such a table, Khot presents (Ruling out a PTAS for Graph Min-Bisection, Dense k-Subgraph, and Bipartite Clique, 2005) a PCP which simply reconstructs the univariate polynomial from random points in addition to the random line.
• Uriel Feige's conjectured inequality on sums of independent nonnegative random variables.
• What equivalences of PCP hold for classes other than NP? Condon, Feigenbaum, Lund, and Shor gave in 1997 (Random Debaters and the Hardness of Approximating Stochastic Functions) an equivalence for PSPACE under the name of probabilistically checkable debate systems (PCDS). In this system, the proof which we verify is written by two alternating competing agents: one wishing to prove that the given instance is positive (existential bits) and one wishing to prove that the instance is negative (universal bits). As with PCP, they found that PCDS(0, n^O(1)) = PCDS(O(log n), O(1)). Furthermore, the result holds if we substitute one of the agents by one that makes random choices. Chris Uman's Ph.D. thesis extended PCP in a similar manner to the polynomial hierarchy, the second level in particular, and gave a host of previously unknown inapproximability results.
• What additional class relations are there for self-reducible PSPACE-easy optimization problems with polynomial-time interpretable "policies"?
• Under what conditions is there a distribution D for a problem P such that if P is average-case easy for some complexity class under D, then P is average-case easy for some complexity class under every distribution in some ensemble? (e.g. polynomial-time computable distributions). If the ensemble contains every distribution, then it has been shown that there are distributions as hard as the worst-case complexity (see Ming Li and Paul M.B. Vitanyi, 1989, Average Case Complexity under the Universal Distribution Equals Worst Case Complexity and Dan Gutfreund, 2006, Worst-Case Vs. Algorithmic Average-Case Complexity in the Polynomial-Time Hierarchy). For a general introduction, see e.g. Luca Trevisan's survey on average-case complexity. There are similar questions about smoothed analysis.
• Greedy superstring conjecture: is the greedy algorithm for the shortest superstring problem a 2-approximation? It is currently only known to be a 4-approximation and no better than a 2-approximation. The best known polynomial-time algorithm is a 2.5-approximation. Plenty of room for improvement, but these problems have been studied by smart people for decades now. Google

Metaresearch/planning

How much does your surname affect your scientific career?
Some paper citation graphs
Papers most likely to appear in Your citations. Coming.

Some Propositions Easily Shown but Less Well-known

Some Propositions Easily Shown but Less Well-known
I list here some interesting and fundamental facts in theoretical computer science. These facts are easily shown, yet people seem surprised when first confronted with them.

Scratchpad

(answers most appreciated)
* Is there a "non-trivial" oracle which equals itself with probability 1, i.e. P(B^A = B) = 1?
* What can we say about non-relativized worlds by studying random oracles?
* What is the relation between exact simulation of the three-body problem and a closed form solution? Does one imply the other?