PhD Seminar • Algorithms and Complexity: Raising Permutations to Powers in PlaceExport this event to calendar

Wednesday, March 21, 2018 — 1:30 PM EDT

Hicham El-Zein, PhD candidate
David R. Cheriton School of Computer Science

Given a permutation of $n$ elements, stored as an array, we address the problem of replacing the permutation by its $k^{\mathrm{th}}$ power. We aim to perform this operation quickly using $o(n)$ bits of extra storage. To this end, we first present an algorithm for inverting permutations that uses $O(\lg^2 n)$ additional bits and runs in $O(n\lg n)$ worst case time. This result is then generalized to the situation in which the permutation is to be replaced by its $k^{\mathrm{th}}$ power.

An algorithm whose worst case running time is $O(n\lg n)$ and uses $O(\lg^2 n + \min\{k\lg n,n^{\rfrac{3}{4}+\epsilon}\})$ additional bits is presented.

Location 
DC - William G. Davis Computer Research Centre
1304
200 University Avenue West

Waterloo, ON N2L 3G1
Canada

S M T W T F S
27
28
29
30
31
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
  1. 2019 (237)
    1. December (5)
    2. November (23)
    3. October (16)
    4. September (20)
    5. August (18)
    6. July (12)
    7. June (23)
    8. May (23)
    9. April (32)
    10. March (25)
    11. February (16)
    12. January (24)
  2. 2018 (220)
    1. December (16)
    2. November (19)
    3. October (26)
    4. September (22)
    5. August (17)
    6. July (20)
    7. June (13)
    8. May (25)
    9. April (34)
    10. March (24)
    11. February (3)
    12. January (1)
  3. 2017 (36)
  4. 2016 (21)
  5. 2015 (36)
  6. 2014 (33)
  7. 2013 (23)
  8. 2012 (4)
  9. 2011 (1)
  10. 2010 (1)
  11. 2009 (1)
  12. 2008 (1)