## To do as of Sep 8:

1. Liren's SVM results look very promising. We are missing the proof of the incentive part (We want to show Alice are incentivized to truthfully report on all queries.). Currently it's only true with many conditions (We need to assume Alice's objective function, the number of data points).
2. Currently the project-to-1-d protocol is only applied at the end. We can try to do it in every round for only points labeled by Alice.
3. Can also try synthetic data, e.g. two Gaussian clusters etc
4. e-discovery has two features
- Transductive (similar to semi-supervise but different, see p19 of [this slides](https://pages.cs.wisc.edu/~jerryzhu/pub/sslicml07.pdf))
- Data is imbalanced and we care about recall much more than other things (precision etc)
5. Seems Maura is only using these two features. No domain knowledge. There should be a methodology paper if it works in general. For example are they just using [transductive SVM](https://www.shane.st/teaching/572/win20/slides/14_transductive-learning.pdf)? Does the project-to-1-d protocol add trustworthiness to any such learning algorithm?
5. Back to separable case, simulation shows the number of critical points is in a reasonable range. In contrast, the number of extremal points (of a point cloud) grows faster in dimension. In my opinion, we would include this only if we fail to improve the incentive part for the non-separable case. It remains a curious fact, but less important for the paper.

## Critical points code
Convex hull problem has many versions
http://www.csun.edu/~ctoth/Handbook/chap26.pdf

Python code uses Qhull which covers faces

Our desired version is called redundancy blah, which can be solved by n LP problems which is implemented in [julia](https://juliapolyhedra.github.io/Polyhedra.jl/stable/generated/Convex%20hull%20of%20a%20set%20of%20points/#Convex-hull-in-higher-dimension) basically $n^2d$ time

THere is a simple speed up to $n|V|d$ time
https://kenclarkson.org/os/t.pdf

THere's another implemented [algo](http://proceedings.mlr.press/v84/awasthi18a.html)

Triangle algo is an alternative to simplex algorithm
Q: does ALTA implement Clarkson trick

their code
https://github.com/yikaizhang/AVTA
quick_hull_AVTA.m is the function
AVTA_eps.m implements their algorithm

Expected number of vertices of $n$ Gaussian points = $(\log n)^{\frac{d-1}{2}}$ if $n\gg d$

https://www2.mathematik.tu-darmstadt.de/~stochastik/SpringSchool2019/lecture4.pdf