Efficient ReliK 4 Sampling Optimization
What is heur? By default, heur is set to binomial. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146def binomial(u: str, v: str, M: nx.MultiDiGraph, models: list[object], entity_to_id_map: object, relation_to_id_map: o ...
丹麦语 DU 3.3 10 Job og kompetencer
Jobannoncer ansvarsbevidst -, -e 负责任的，有责任感的 gå-på-mod -et 主观能动性 kundskab -en, -er, -erne 认知，知识 så hurtigt som muligt 越快越好 weekendvagt 值周末班 ansigt -et, -er, -erne 脸，面部 udadtil 外部的 præsentabel -t, præsentable 像样的，体面的 serviceminded -, -e 服务态度好的 selvstændig = selbständig 自主的，独立的 afvekslende = abwechselnd 交替的 gyldig -t, -e = gültig 有效的 opholds- og arbejdstilladelse -n, -r, -rne 居留和工作许可 afløser -en, -e, -ne 继承人，替代者 vikariat -et, -er, -erne 临时工 tiltrædelse -n, -r, -rne 担任，加入 forlængelse -n, -r, -rne 延 ...
算法和计算复杂度 12 PCP-based Inapproximability
For MAXCLIQUEMAXCLIQUEMAXCLIQUE problem. A constant factor polynomial-time approximation algorithm doesn’t exist unless NP∈DTIME(2(logn)O(1))NP\in DTIME(2^{(\log n)^{O(1)}})NP∈DTIME(2(logn)O(1)), based on the theorem that NP⊆PCP((logn)O(1),(logn)O(1))NP\subseteq PCP((\log n)^{O(1)},(\log n)^{O(1)})NP⊆PCP((logn)O(1),(logn)O(1)). Use a different approach the final PCPPCPPCP theorem implies that a constant factor polynomial-time approximation algorithm for MAXE3SATMAXE3SATMAXE3SAT doesn’t exist ...
算法和计算复杂度 13 Random Access Machine
More precise model Problem of integer multiplication. Registers can contain arbitrary integers. Consider repeated squaring to number 222. After just nnn multiplications, the resulting number is 22n2^{2^n}22n, a doubly exponential large number in nnn. This requires exponential number of bits. A RAM has an infinite sequence of registers each able to contain an arbitrary non-negative integer. Machine is controlled by a program consisting of a list of instructions. Registers can be added or subtrac ...
Fair AI/ML 5 PROP in Non-Centroid Clustering
Read the paper Proportional Fairness in Non-Centroid Clustering by Caragiannis et al. This paper was accepted in NeurIPS 2024! Introduction nnn points, kkk clusters C=(C1,⋯ ,Ck)C=(C_1,\cdots,C_k)C=(C1,⋯,Ck), distance metric ddd. kkk-means objective: ∑i=1k1∣Ci∣⋅∑x,y∈Cid(x,y)2\sum_{i=1}^k\frac{1}{|C_i|}\cdot\sum_{x,y\in C_i}d(x,y)^2∑i=1k∣Ci∣1⋅∑x,y∈Cid(x,y)2. Scenario in which there are no cluster centers. Question: Can we obtain PROP guarantee for non-centroid clustering? Do the algorithm ...
丹麦语 DU 3.3 9 Jobsøgning
Edison søger job krævende 苛求的 et par måneder 几个月 indtil 直到 vikariat -et, -er, -erne 临时职位 kvalifikation -en, -er, -erne 资格 rutinepræget -, …prægede 固定程序的，无脑的 utilfredsstillende 令人不满意的 afvekslende adv 交互，交替 udfordrende 有挑战的 allerførst -, -e 首先，第一 personlighed -en, -er, -erne 个性，性格 kompetence -n, -r, -rne 能力，权力，专长 overfladisk -, -e 皮毛的，浅层次的，表面的 nysgerrig -t, -e 好奇的 indadvendt -, - 内向的 udadvendt -, - 外向的 målrettet -, målrettede 坚定的，果断的 resultatorienteret 以结果为导向的 holdspiller -en, -e, -ne 团队成员 mene 认 ...
算法和计算复杂度 11 Probabilistic Checkable Proofs
Proof systems where a polynomial-time probabilistic verifier can spot-check a given written proof by inspecting a few randomly selected symbols of the proof. Cost: Introducing some error. 📖Definition 48 (PCP verifier). A (non-adaptive) PCP verifier VVV is a polynomial-time probabilistic Turing machine equipped with an additional random access proof tape together with a write-only query tape and a read-only answer tape. Two additional states: query state and continue state. The symbols on the pr ...
Fair AI/ML 4 Endeavor to Bridge Gap between 2 and 2.414
We dedicated to solve the open problem left by Greedy Capture: Is there an algorithm that has better PROP guarantee 2≤ρ≤1+22\le\rho\le1+\sqrt22≤ρ≤1+2? My Initial Immature Idea Do some fine-tuning on results of Greedy Capture. Pseudo code X←X\getsX← Greedy Capture(N,M,k)(\mathcal N,\mathcal M,k)(N,M,k) N←∅N\gets\emptyN←∅ // NNN denotes “free” data points while ∃\exist∃ 2-approximate Block Coalition Nbc←N_{bc}\getsNbc← all data points in that 2-approx Block Coalition Xbc←X_{bc}\getsXbc← all ...
丹麦语 DU 3.3 7-8 Arbejdspladskultur
有趣的表达： tisse i bukserne for at holde varmen 直译：在裤子里撒尿来保持温暖 意译：饮鸩止渴 Johanna, Manu og Anya skilte -r, -de, -t 吹嘘，炫耀，张贴 pinlig -t, -e 尴尬的 omvendt -, -e 相反 eks. I Indien er det lige omvendt. titel titlen, titler, titlerne 头衔 hierarki -et, -er, -erne 层次结构；阶层 almindelig -t, -e 常见的，普通的 tvivl -en 怀疑 tvivl om at + SÆTNING/NOGET/hv+SÆTNING komme i tvivl forventning -en, -er, -erne 期望 overholde -r, …holdt, …holdt 遵守 erklæring -en, -er, -erne 声明 = Erklärung er vant til = vænne sig til 习惯于 egentlig -t, -e ...
算法和计算复杂度 10 Interactive Proofs
Interactive Turing Machine 📖Definition 44 (interactive Turing machine). An interactive TM MMM is a probabilistic TM equipped also with a write-only query tape and a read-only answer tape, and has two new special states, a query state and a continue state. The symbols allowed on the query and answer tape are given by a communication alphabet Λ\LambdaΛ. When MMM enters the query state, the contents mmm of the query tape as a message mmm sent by MMM. We say that we send a reply rrr to mmm by perf ...