1 of 179

The Price Of Differential Privacy under Continual Observation

Satchit Sivakumar

Adam Smith

Sofya Raskhodnikova

Palak Jain

Iden Kalemaj

2 of 179

Aggregate Statistics on Sensitive Dynamic Data

2

3 of 179

Batch Model�

4 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

5 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

6 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

7 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

8 of 179

Privacy:

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

9 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Privacy:

10 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Privacy:

11 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Privacy:

12 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Privacy:

13 of 179

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Batch Model�

Privacy:

14 of 179

Accuracy:

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Batch Model�

Privacy:

15 of 179

.

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

Batch Model�

Accuracy:

Privacy:

16 of 179

.

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

Batch Model�

Accuracy:

Privacy:

17 of 179

.

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

Batch Model�

Accuracy:

Privacy:

18 of 179

.

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

Batch Model�

Accuracy:

Privacy:

19 of 179

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Batch Model�

Accuracy:

Privacy:

20 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Accuracy:

Privacy:

21 of 179

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Batch Model�

Accuracy:

Privacy:

22 of 179

Batch Model�

Continual Release Model�

[Dwork Naor Pitassi Rothblum 2010]

[Chan Shi Song 2010]

.

Accuracy:

Privacy:

23 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

Summation:

24 of 179

6


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

Batch Model

Summation:

25 of 179

Batch Model

6


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

Summation:

26 of 179

1

6

1

2

Continual Release Model


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

Summation:

Continual Release Model

27 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

1

6

1

2

Summation:

Continual Release Model

Recompute every

time-step

28 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

1

6

1

2

Summation:

Continual Release Model

29 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

1

6

1

2

Summation:

Continual Release Model

30 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

1

6

1

2

Summation:

Continual Release Model

31 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

1

6

1

2

Summation:

Continual Release Model

32 of 179

Natural approach:

Binary Tree

Mechanism

Summation:


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

33 of 179

Natural approach:

Binary Tree

Mechanism

Summation:


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

0

1

0

1

0

1

0

1

0

1

34 of 179

Natural approach:

Binary Tree

Mechanism

Summation:


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

0

1

0

1

2

1

0

1

0

1

0

1

0

1

0

1

35 of 179

Natural approach:

Binary Tree

Mechanism

Summation:


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

0

1

0

1

2

3

1

3

1

0

1

0

1

0

1

0

1

0

1

36 of 179

Summation:

Natural approach:

Binary Tree

Mechanism


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

0

1

0

1

2

3

1

3

4

1

0

1

0

1

0

1

0

1

0

1

37 of 179

Summation:

Natural approach:

Binary Tree

Mechanism


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

38 of 179

Summation:

Natural approach:

Binary Tree

Mechanism


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

39 of 179

Summation:

Natural approach:

Binary Tree

Mechanism


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

40 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

Binary Tree

Mechanism

41 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Binary Tree

Mechanism

42 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Binary Tree

Mechanism

43 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

1

2

1

0

1

2

1

3

4

1

0

1

0

1

0

1

0

1

Natural approach:

Summation:

0

1

3

1

4

8

0

1

Binary Tree

Mechanism

44 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Accuracy:

Summation:

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

Binary Tree

Mechanism

45 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

Binary Tree

Mechanism

46 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

Binary Tree

Mechanism

47 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

Binary Tree

Mechanism

48 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Natural approach:

Summation:

1

2

1

0

1

2

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

0

3

0

Binary Tree

Mechanism

49 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Natural approach:

Binary Tree

Mechanism

This mechanism can be applied quite generally:

50 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Natural approach:

Binary Tree

Mechanism

This mechanism can be applied quite generally:

differentially private online learning: �[Jain Kothari Thakurta ‘12] [Smith Thakurta ‘13] [Agarwal Singh ’17]

51 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Natural approach:

Binary Tree

Mechanism

This mechanism can be applied quite generally:

differentially private online learning: �[Jain Kothari Thakurta ‘12] [Smith Thakurta ‘13] [Agarwal Singh ’17]�
weighted sums and sums of real-valued data: �[Bolot Fawaz Muthukrishnan Nikolov Taft ‘13] �[Perrier Asghar Kaafar ‘19]

52 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Natural approach:

Binary Tree

Mechanism

This mechanism can be applied quite generally:

differentially private online learning: �[Jain Kothari Thakurta ‘12] [Smith Thakurta ‘13] [Agarwal Singh ’17]�
weighted sums and sums of real-valued data: �[Bolot Fawaz Muthukrishnan Nikolov Taft ‘13] �[Perrier Asghar Kaafar ‘19]

graph problems:�[Song Little Mehta Vinterbo Chaudhuri ‘17]�[Fichtenberger Henzinger Ost ‘19]

53 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Natural approach:

Binary Tree

Mechanism

This mechanism can be applied quite generally:

differentially private online learning: �[Jain Kothari Thakurta ‘12] [Smith Thakurta ‘13] [Agarwal Singh ’17]�
weighted sums and sums of real-valued data: �[Bolot Fawaz Muthukrishnan Nikolov Taft ‘13] �[Perrier Asghar Kaafar ‘19]

graph problems:�[Song Little Mehta Vinterbo Chaudhuri ‘17]�[Fichtenberger Henzinger Ost ‘19]

counting distinct elements:�[Bolot Fawaz Muthukrishnan Nikolov Taft ‘13]�[Jain Kalemaj Raskhodnikova Sivakumar Smith ‘23]

54 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0
1
1

Summation:

1

2

0

1

0

1

2

3

1

3

4

8

1

0

1

0

1

0

1

0

1

0

1

Natural approach:

Binary Tree

Mechanism

This mechanism can be applied quite generally:

differentially private online learning: �[Jain Kothari Thakurta ‘12] [Smith Thakurta ‘13] [Agarwal Singh ’17]�
weighted sums and sums of real-valued data: �[Bolot Fawaz Muthukrishnan Nikolov Taft ‘13] �[Perrier Asghar Kaafar ‘19]

graph problems:�[Song Little Mehta Vinterbo Chaudhuri ‘17]�[Fichtenberger Henzinger Ost ‘19]

counting distinct elements:�[Bolot Fawaz Muthukrishnan Nikolov Taft ‘13]�[Jain Kalemaj Raskhodnikova Sivakumar Smith ‘23]

55 of 179

Conjecture: All sensitivity one functions can be solved with only a logarithmic error blowup?

56 of 179

Conjecture: All sensitivity one functions can be solved with only a logarithmic error blowup?

57 of 179

Conjecture: All sensitivity one functions can be solved with only a logarithmic error blowup?

58 of 179

Conjecture: All sensitivity one functions can be solved with only a logarithmic error blowup?

59 of 179

Conjecture: All sensitivity one functions can be solved with only a logarithmic error blowup?

60 of 179

Conjecture: All sensitivity one functions can be solved with only a logarithmic error blowup?

61 of 179

.

Privacy in the Continual Release Model

62 of 179


1
0
1
1
0
0
0
1
0
1
0
0
1
0

.

Natural approach:

1

6

1

2

Summation:

63 of 179

.

Natural approach:


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation:

64 of 179

.


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

MaxSum:

65 of 179

.


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

MaxSum:

66 of 179

.


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

MaxSum:

67 of 179

.


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

MaxSum:

68 of 179

.


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

Can we do better? No!

MaxSum:

69 of 179

.


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

Summation

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

Can we do better? No!

MaxSum:

70 of 179

Summation


1	1	0	0
0	0	1	1
1	0	0	0
1	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
1	1	0	0
0	1	0	0
1	1	0	0
0	0	0	1
0	0	0	1
1	0	0	1
0	0	0	1

.

Our Work

Can we do better? No!

MaxSum:

[Dwork Naor Pitassi Rothblum ‘10]

[Chan Shi Song ‘10]

71 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

.

MaxSum:

72 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1
2	5	3	6

.

6

MaxSum:

Batch model:

Learn information about one coordinate sum.

Intuition Behind Hardness

73 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

MaxSum:

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

74 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

MaxSum:

2

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

75 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

MaxSum:

2

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

76 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

MaxSum:

2

3

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

77 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

MaxSum:

2

3

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

78 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

MaxSum:

2

3

5

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

79 of 179


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

.

MaxSum:

2

3

5

6

Intuition Behind Hardness

Batch model:

Learn information about one coordinate sum.

Continual release model:

Learn information about many coordinate sums!

80 of 179

Key Idea for Lower Bound:

MaxSum:

81 of 179

.

MaxSum:


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

82 of 179

.

MaxSum:


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

83 of 179

.

MaxSum:


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1

84 of 179

Overview of Reduction

MaxSum:

85 of 179


0	1	1
1	0	1
0	0	0

dataset

Overview of Reduction

MaxSum:

86 of 179

estimate of first coordinate sum


0	1	1
1	0	1
0	0	0
1	0	0
1	0	0
1	0	0

dataset

get a sum

Overview of Reduction

MaxSum:

87 of 179

estimate of first coordinate sum


0	1	1
1	0	1
0	0	0
1	0	0
1	0	0
1	0	0
-1	0	0
-1	0	0
-1	0	0

dataset

get a sum

refresh

Overview of Reduction

MaxSum:

88 of 179

estimate of first coordinate sum

estimate of second coordinate sum


0	1	1
1	0	1
0	0	0
1	0	0
1	0	0
1	0	0
-1	0	0
-1	0	0
-1	0	0
0	1	0
0	1	0
0	1	0

dataset

get a sum

refresh

Overview of Reduction

MaxSum:

89 of 179

estimate of first coordinate sum

estimate of second coordinate sum


0	1	1
1	0	1
0	0	0
1	0	0
1	0	0
1	0	0
-1	0	0
-1	0	0
-1	0	0
0	1	0
0	1	0
0	1	0

dataset

get a sum

refresh

repeat for remaining coordinates!

Overview of Reduction

MaxSum:

90 of 179

Lower Bound


0	1	1
1	0	1
0	0	0

91 of 179


0	1	1
1	0	1
0	0	0

Lower Bound

92 of 179


0	1	1
1	0	1
0	0	0

Lower Bound

93 of 179


0	1	1
1	0	1
0	0	0

Lower Bound

94 of 179


0	1	1
1	0	1
0	0	0

Lower Bound

95 of 179


0	1	1
1	0	1
0	0	0

Lower Bound

96 of 179

CountDistinct:

- insert

- delete

Item

.

97 of 179

CountDistinct:

- insert

- delete

Item

.

98 of 179

CountDistinct:

- insert

- delete

Item

.

99 of 179

Item

.

CountDistinct:

- insert

- delete

100 of 179

Item

.

CountDistinct:

- insert

- delete

101 of 179

Item

.

CountDistinct:

- insert

- delete

102 of 179

Item







0

.

CountDistinct:

- insert

- delete

103 of 179

Item







0

.

CountDistinct:

- insert

- delete

104 of 179

Item







1

.

CountDistinct:

- insert

- delete

105 of 179

Item







1

.

CountDistinct:

- insert

- delete

106 of 179

Item







1

.

CountDistinct:

- insert

- delete

107 of 179

Item







1

.

CountDistinct:

- insert

- delete

108 of 179

Item







1

.

CountDistinct:

- insert

- delete

109 of 179

Item







1

.

Can we do better?

CountDistinct:

- insert

- delete

110 of 179

Item







1

.

Can we do better? Polynomial in T necessary!

CountDistinct:

- insert

- delete

111 of 179

Item







1

.

Can we do better? Polynomial in T necessary!

Our Work

CountDistinct:

- insert

- delete

112 of 179

CountDistinct:

- insert

- delete

113 of 179

Key Idea for Lower Bound

CountDistinct:

- insert

- delete

114 of 179

Inner Products in batch model:

CountDistinct:

- insert

- delete

115 of 179

Inner Products in batch model:

CountDistinct:

- insert

- delete


1
0
0

1
1
0

.

116 of 179

Inner Products in batch model:

CountDistinct:

- insert

- delete


1
0
0

1
1
0

.


0
1
0
0
1
1
0

117 of 179

Inner Products in batch model:

CountDistinct:

- insert

- delete


1
0
0

1
1
0

.


0
1
0
0
1
1
0

118 of 179

Inner Products in batch model:

CountDistinct:

- insert

- delete


1
0
0

1
1
0

.


0
1
0
0
1
1
0

119 of 179

Inner Products in batch model:


0
1
0
0
1
1
0

CountDistinct:

- insert

- delete


1
0
0

1
1
0

.


0
1
0
0
1
1
0

120 of 179

Inner Products in batch model:


0
1
0
0
1
1
0

CountDistinct:

- insert

- delete


1
0
0

1
1
0

.


0
1
0
0
1
1
0

121 of 179

CountDistinct:

- insert

- delete

122 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.

123 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.

124 of 179

CountDistinct:

- insert

- delete

Index transformation


1
0

0
1
1
0

.

125 of 179

CountDistinct:

- insert

- delete

Index transformation

For data entries that are 1, insert their index


1
0

0
1
1
0

.

126 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.

Index transformation


1

For data entries that are 1, insert their index

127 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.

Index transformation


1

For data entries that are 1, insert their index
For data entries that are 0, add bot.

128 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.

Index transformation


1

129 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


0
1

0
1
1
0

Index transformation

130 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


0
1

0
1
1
0


1

Index transformation

131 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


0
1

0
1
1
0


1

132 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


0
1

0
1
1
0


1

133 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


0
1

0
1
1
0


1

134 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


0
1

0
1
1
0


1

135 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


1


0
1

0
1
1
0

136 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


1


0
1

0
1
1
0

137 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


1


0
1

0
1
1
0

138 of 179

CountDistinct:

- insert

- delete


1
0

0
1
1
0

.


1


0
1

0
1
1
0

139 of 179

Overview of Reduction

140 of 179

Overview of Reduction


0
1
0


0
1
0


1
1
0

Inputs:

141 of 179

Overview of Reduction



2


0
1
0


0
1
0


1
1
0

Inputs:

142 of 179


0
1
0

.�.


0
1
0

Overview of Reduction


1
1
0



2

Inputs:

143 of 179

.�.

Overview of Reduction



2

1
2


0
1
0


0
1
0


1
1
0

Inputs:

144 of 179

.�.

Overview of Reduction

.�.



2

1
2


0
1
0


0
1
0


1
1
0

Inputs:

145 of 179

.�.

Overview of Reduction

.�.



2

1
2


0
1
0


0
1
0


1
1
0

Inputs:

146 of 179

.�.

Overview of Reduction



2

1
2

1
2

.�.

Delete

.�.


0
1
0


0
1
0


1
1
0

Inputs:

147 of 179


0
1
0

.�.


0
1
0

Overview of Reduction


1
1
0



2

1
2

1
2


2

Inputs:

.�.

Delete

148 of 179


0
1
0

.�.


0
1
0

Overview of Reduction


1
1
0



2

1
2

1
2


2

Inputs:

.�.

Delete

.�.

149 of 179


0
1
0

.�.


0
1
0

Overview of Reduction


1
1
0



2

1
2

1
2


2

Inputs:

.�.

Delete

.�.

150 of 179


0
1
0

.�.


0
1
0

Overview of Reduction


1
1
0



2

1
2

1
2


2

Inputs:

.�.

Delete

.�.

repeat for remaining O(n) queries!

151 of 179

CountDistinct:

- insert

- delete

152 of 179

Lower Bound

CountDistinct:

- insert

- delete

153 of 179

Lower Bound


0
1
0

CountDistinct:

- insert

- delete

154 of 179

Lower Bound


0
1
0

CountDistinct:

- insert

- delete

155 of 179

Lower Bound


0
1
0

CountDistinct:

- insert

- delete

156 of 179

Lower Bound


0
1
0

CountDistinct:

- insert

- delete

157 of 179

Lower Bound


0
1
0

CountDistinct:

- insert

- delete

158 of 179

Lower Bound


0
1
0

CountDistinct:

- insert

- delete

159 of 179

CountDistinct:

- insert

- delete

160 of 179

What to do when faced with strong lower bounds?

CountDistinct:

- insert

- delete

161 of 179

What to do when faced with strong lower bounds?

Cry��

��

CountDistinct:

- insert

- delete

162 of 179

What to do when faced with strong lower bounds?

Cry��

Lower bounds are worst case- perhaps we can do better in many cases? ��

CountDistinct:

- insert

- delete

163 of 179

CountDistinct:

- insert

- delete

Maximum Flippancy

164 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

165 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Item

.

166 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Item

.

Flippancy of all items is 2

Maximum flippancy is 2

167 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Item

.

Flippancy of all items is 2

Maximum flippancy is 2

168 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Maximum flippancy is small for many natural streams!

169 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Maximum flippancy is small for many natural streams!

170 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Maximum flippancy is small for many natural streams!

Does not improve for low flippancy streams

171 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Maximum flippancy is small for many natural streams!

Does not improve for low flippancy streams

Our Result [JKRSS NeurIPS’23]:

172 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Maximum flippancy is small for many natural streams!

Does not improve for low flippancy streams

Our Result [JKRSS NeurIPS’23]:

173 of 179

Maximum Flippancy

Maximum Flippancy of a stream: Maximum number of times that an item switches between being present and being absent in the stream

CountDistinct:

- insert

- delete

Maximum flippancy is small for many natural streams!

Does not improve for low flippancy streams

Our Result [JKRSS NeurIPS’23]:

Tight in terms of flippancy!

174 of 179

Open Problems

175 of 179

The following optional slides are about the setting with adaptively chosen inputs.

176 of 179

.

Privacy in the Continual Release Model

…

Adaptively Chosen Inputs

177 of 179

…

Adaptively Chosen Inputs

Privacy Game

178 of 179

Privacy Game

179 of 179

Adaptively Chosen Inputs

Proof Technique for the Binary Tree Mechanism


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1
2	5	3	6


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1
2	5	3	6


1	1	0	0
1	0	1	1
0	0	0	0
0	0	1	1
0	0	1	0
0	0	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	1	0	0
0	0	0	1
0	0	0	1
0	0	0	1
0	0	0	1
2	5	3	6