# Vinayak Pathak

Waterloo

Age: 27

I am a Masters student in computer science at the University of Waterloo. My research interests are computational and combinatorial geometry.
 Nov 1 awarded Supporter Oct 31 awarded Informed Aug 17 awarded Yearling Aug 17 awarded Yearling May 7 awarded Yearling Mar 26 awarded Yearling Mar 17 comment Sorting using a black box@JɛﬀE: Yes, great, that definitely looks simpler than my construction. Mar 17 comment Sorting using a black boxIn the last step of the algorithm partition(): "Partition all m elements around X", won't this use m additional comparisions? Mar 17 comment Sorting using a black boxI think we can even get $O(\sqrt{n}\log n)$ using AKS's sorting network. Their network can be thought of as an instantiation of your model where the black box can sort blocks of size 2. Their algorithms uses $O(\log n)$ rounds, each round calling the 2-sorter $O(n)$ times. One "round" of $O(n)$ 2-sorters can be easily simulated with $O(\sqrt{n})$ $\sqrt{n}$-sorters. Feb 27 accepted Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions? Feb 19 awarded Nice Question Feb 18 awarded Citizen Patrol Feb 18 revised Good seating arrangements for sequence of meals and tables of size k for a group of peopleRemoved the previous edit. Feb 18 revised Good seating arrangements for sequence of meals and tables of size k for a group of peopleAdded a better bound. Feb 18 answered Good seating arrangements for sequence of meals and tables of size k for a group of people Feb 16 comment Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?@SureshVenkat Thanks for the tip. But I will still be stuck with finding the coefficient of $x^k$ in this really complicated polynomial in terms of $n$ and $k$ and I don't see how to do that. Feb 15 asked Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions? Dec 4 awarded Caucus Nov 16 awarded Supporter Nov 15 revised Element distinctness in O(n) time?Edited the link for the reference.