min hjemmeside

First part of lecture notes on prophet inequality and secretary problem is by Anupam Gupta (CMU) Prophet inequalities and Secretary problems are 2 classes of problem where online decision-making meets stochasticity: in the first set of problems the inputs are random variables, whereas in the second one the inputs are worst-case but revealed to the algorithm (aka decision maker) in random order. Here are some results, proofs and techniques about them. The Prophet Inequality 在之前的算法博弈论课上学过，具体可以参考我 ...

GNN - graph neural networks Intuition: how to propagate information over the neighbors in a non-linear manner. Graph Embeddings as Matrix Factorization Linear embeddings correspond to SVD of the similarity matrices chosen in the objective. For adjacency-based similarity, the best linear ddd-dimensional embedding corresponds to the projection of the dataset into the ddd directions associated to the top-ddd singular values: if SVD(A)=UΣV⊤then the embedding matrix Z=UdΣd\text{if }SVD(\mathbf A)=\m ...

Inhalt Wissenschaft für Kinder Wer einmal lügt, … Ist da jemand? Gute Nacht! 5-1 Wer Wissen schafft, macht Wissenschaft verschlafen 因睡觉而耽误；睡眠过度 die Längeneinheit-en 长度单位 das/der Millimeter 毫米 das/der Femtometer 飞米 1 飞米 = 10-15 米 das/der Nanometer 纳米 der Benzinmotor-en 汽油引擎 der Speck-e 皮下脂肪；腌肉，熏肉 die Lebenserwartung 预计寿命 die Mücke-n 蚊子 der Flügel- 翅膀 5-2 Wissenschaft für Kinder (1) lenken 操纵，控制 gespannt 集中注意力的 bestmöglich 尽可能好的 ausgewechselt 判若两人的 jmdm an den Lippen hängen 仔细听某人，集中注意力听某人 die ...

Objective: Investigate methods for computing allocations satisfying both EF1 and PO. Activities: Review the paper Finding Fair and Efficient Allocations. Caragiannis et al has established the result: for additive valuations, there always exists an allocation that is EF1 + PO by maximizing Nash Social Welfare. However, computing MNW is NP-Hard. This paper: develop a pseudo-polynomial time algorithm for finding EF1 + PO. When valuations are bounded, the algorithm is polynomial time. For additive ...

读音辨析 hun - hund man - mand - men - mænd 不加 清音 d 的时候，读的舒缓一点，加了 d 的单词需要读快一点，狠一点 Selvom 中的 v 不发音 en have / haven 花园 et hav / havet 大海 en havn / haven 港口 at have 有 Kirsten har et jernhelbred helbred 健康 通常指一个人的身体健康或心理健康状况 f. eks. Min son har et godt helbred. jernhelbred “铁打的”健康身体 rask 健康的，充满活力的 bl.a. = blandt andet 除其他事项外 hygge sig 找乐子 er fuld af energi 充满了能量 i god form 保持好身材 cerut -ten - ter -terne 香烟 sundhed 健康 涵盖了健康的各个方面，包括生活方式、饮食、运动等 Hvad gør du for at holde dig rask? 为了保持健康，你会做啥？ Hvad gør ...

Main problem with graphs: lack of predefined node ordering. Graph is non-Euclidean: the distance among two nodes does not depend on the coordinates of the nodes. Origin idea of graph embedding: graph could become a set of multi-dimensional points in which Euclidean distances represent similarities among the nodes. 2 methods of embedding: Linear embedding: linear transformation of the edges. Random-walk embedding: preserving the probability that a node is reachable from another node. Linear Em ...

After reading the paper Optimal Bounds on the Price of Fairness for Indivisible Goods to know the notion of Price of Fairness and the paper New Fairness Concepts for Allocating Indivisible Items to adapt new fairness notions EEFX and MXS, it is natural to consider the left open problem: What is the PoF for EEFX and MXS? The Relation between EFX, EEFX, MXS, PROP1 It is not hard to say that EFX⊂EEFX⊂MXS⊂PROP1EFX\sub EEFX\sub MXS\sub PROP1 EFX⊂EEFX⊂MXS⊂PROP1 Every EFX allocation is EEFX allocatio ...

Lecture notes by Kasper. This lecture: different approaches used to speed up the JL transform. Recall: classic JL transform works by drawing a random matrix AAA with coordinates i.i.d. either N(0,1)\mathcal N(0,1)N(0,1) or uniform random among {−1,+1}\{-1,+1\}{−1,+1} and then embedding a vector xxx to m−1/2Axm^{-1/2}Axm−1/2Ax. m=O(ϵ−2log⁡n)m=O(\epsilon^{-2}\log n)m=O(ϵ−2logn) if one wants to preserve all pairwise distances to within (1±ϵ)(1\pm\epsilon)(1±ϵ) and embedding time is O(dm)O(dm)O(dm). ...

PageRank as a fundamental tool in graph mining, connections to Markov process and linear algebra. Random Walk PageRank An algorithm that provides a score to each web page. It follows: Each link’s vote is proportional to the importance of its source page. If node jjj with importance rjr_jrj​ has nnn out links, each of the jjj’s neighbors gets rj/nr_j/nrj​/n votes. Page jjj’s own importance is the sum of the votes on its in-links. PageRank can be simply expressed as the sum of the scores of the ...

Objective: Examine the compatibility of EF1 with Pareto-optimality, introducing the concept of EFX. Activities: Read and present the paper The Unreasonable Fairness of Maximum Nash Welfare. Ioannis et al. ACM Transactions on Economics and Computation 2019 It’s worth to mention that Iannis received Kalai Prize 2024 for this paper 🎆 Hint from Iannis: Ignore appendix, experiments. Focus on the proof, paraphrase it in my own words, a easy way! Maximum Nash welfare (abbr. MNW) selects an allocatio ...