Sorting under partial information (without the ellipsoid algorithm)

We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (STOC 1992) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: an O(n2) algorithm performing O(log n·log e(P)) comparisons; an O(n2.5) algorithm performing at most (1+ε) log e(P) + Oε(n) comparisons; an O(n2.5) algorithm performing O(log e(P)) comparisons. All our algorithms are simple to implement. © 2010 ACM.

The temporal dynamics of metacognition: Dissociating task-related activity from later metacognitive processes

In recent years, neuroscience research spent much effort in revealing brain activity related to metacognition. Despite this endeavor, it remains unclear exactly when metacognitive experiences develop during task performance. To investigate this, the current study used EEG to temporally and spatially dissociate task-related activity from metacognitive activity. In a masked priming paradigm, metacognitive experiences of difficulty were induced by manipulating congruency between prime and target. As expected, participants more frequently rated incongruent trials as difficult and congruent trials as easy, while being completely unable to perceive the masked primes. Results showed that both the N2 and the P3 ERP components were modulated by congruency, but that only the P3 modulation interacted with metacognitive experiences. Single-trial analysis additionally showed that the magnitude of the P3 modulation by congruency accurately predicted the metacognitive response. Source localization indicated that the N2 task-related activity originated in the ACC, whereas the P3-interplay between task-related activation and metacognitive experiences originated from the precuneus. We conclude that task-related activity can be dissociated from later metacognitive processing.