算法和计算复杂度 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 ...
Fair AI/ML 3 PROP Fair Clustering Revisited
Read the paper Proportionally Fair Clustering Revisited by Micha et Shah. kkk cluster centers must be placed given nnn points in a metric space. The cost to each point is its distance to the nearest cluster center. This paper: Focus on the case where cluster centers can be placed anywhere in metric space. E.g. L2L^2L2 distance over Rt\mathbb R^tRt, the approximation ratio of greedy capture improves to 222. For L1,L∞L^1,L^\inftyL1,L∞ metric, the approximation ratio remains 1+21+\sqrt 21+2. The p ...
Fair AI/ML 2 PROP Fair Clustering
Read the paper Proportionally Fair Clustering by Chen et al. Abstract nnn points, kkk centers. Proportionality: any n/kn/kn/k points are entitled to form own cluster if there is another center that is closer in distance for all n/kn/kn/k points. Clustering with no justified complaints from any subset of agents. Tradeoff between proportional solutions and kkk-means objective. Introduction In centroid clustering, we want to partition data into kkk clusters by choosing kkk centers and then matchi ...
算法和计算复杂度 9 Circuit Lower Bounds
Parity function is not in AC0AC^0AC0. MAJ∉AC0MAJ\not\in AC^0MAJ∈AC0. NEXP⊈ACC0NEXP\not\subseteq ACC^0NEXP⊆ACC0. Some unknown proposition: whether NP⊆ACC0NP\subseteq ACC^0NP⊆ACC0. whether EXP⊆ACC0EXP\subseteq ACC^0EXP⊆ACC0. whether NEXP⊆TC0NEXP\subseteq TC^0NEXP⊆TC0. whether all languages in NEXPNEXPNEXP can be computed by depth 222 circuits consisting of weighted linear threshold gates. The Razborov-Smolensky Lower Bound The lower bounds for class AC0[pr]AC^0[p^r]AC0[pr], where pp ...
