Taha

Taha

Hi, I am Taha.

Posts by Tags

FR-Dijkstra

And god said let there be dijkstra

18 minute read

Published:

Alright, in this work I want to explain the seminal work of Jittat Fakcharoenphol and Satish Rao in 2006, devising the algorithm of FR-Dijkstra, which is so insightful and meaningful.

Fourier analysis

Lewis weights

Lewis Weights, Leverage Scores, and Whitening — Chapter 2

12 minute read

Published:

This is the second chapter in my series on Sparsifying Sums of Norms. Chapter 1 set up the general problem and briefly mentioned Lewis weights. In the second post of this series on sparsification of the norm, I want to turn to the $\ell_p$ row sampling paper. I’ll be spending a few posts on this one, because I think it is genuinely revealing on the subject it is worth pondering carefully and going through in some detail. The paper relies heavily on the works of Milman and Talagrand(for example), so I may cover those seminal papers too at some point. At a high level, this paper is a vast generalization of the Johnson–Lindenstrauss lemma, with a few extremely technical steps, but the overall theme is clear and elegant. I especially like how they used Talagrand’s result and intuition, and the way they brought in Lewis weights to pull everything together.

Monge arrays

And god said let there be dijkstra

18 minute read

Published:

Alright, in this work I want to explain the seminal work of Jittat Fakcharoenphol and Satish Rao in 2006, devising the algorithm of FR-Dijkstra, which is so insightful and meaningful.

Sobolev spaces

TFNP

approximation algorithms

Probabilistic Tree Embeddings and Hierarchical Cut Decompositions

10 minute read

Published:

As part of my effort to understand the broader literature surrounding the areas I hope to work on in the future, I am studying both foundational papers and contemporary developments. Alongside my primary focus on the work of James R. Lee, I plan to read a number of folklore and classical papers that have shaped the modern theory of metric embeddings.

clustering

combinatorics

Bukh’s Problem on Coloring Random Subgraphs

5 minute read

Published:

So, assume that we have a graph $G = (V, E)$. By $G_p$ for some $p \in (0,1)$ we mean a subgraph such that the probability of each edge appearing in that subgraph is independent with probability $p$.

communication complexity

concentration inequalities

data structures

Dynamic Approximate Nearest-Neighbor Search in Doubling Metrics

18 minute read

Published:

Well, in this blog post we are going to review several papers and understand the techniques that are utilized in order to tackle several problems related to areas such as nearest neighbor problems, the facility location problem, and so on.

doubling dimension

Dynamic Approximate Nearest-Neighbor Search in Doubling Metrics

18 minute read

Published:

Well, in this blog post we are going to review several papers and understand the techniques that are utilized in order to tackle several problems related to areas such as nearest neighbor problems, the facility location problem, and so on.

dynamic algorithms

facility location

functional analysis

generic chaining

geometric hashing

graph algorithms

graph theory

Bukh’s Problem on Coloring Random Subgraphs

5 minute read

Published:

So, assume that we have a graph $G = (V, E)$. By $G_p$ for some $p \in (0,1)$ we mean a subgraph such that the probability of each edge appearing in that subgraph is independent with probability $p$.

high-dimensional algorithms

leverage scores

Lewis Weights, Leverage Scores, and Whitening — Chapter 2

12 minute read

Published:

This is the second chapter in my series on Sparsifying Sums of Norms. Chapter 1 set up the general problem and briefly mentioned Lewis weights. In the second post of this series on sparsification of the norm, I want to turn to the $\ell_p$ row sampling paper. I’ll be spending a few posts on this one, because I think it is genuinely revealing on the subject it is worth pondering carefully and going through in some detail. The paper relies heavily on the works of Milman and Talagrand(for example), so I may cover those seminal papers too at some point. At a high level, this paper is a vast generalization of the Johnson–Lindenstrauss lemma, with a few extremely technical steps, but the overall theme is clear and elegant. I especially like how they used Talagrand’s result and intuition, and the way they brought in Lewis weights to pull everything together.

measure theory

metric embeddings

Probabilistic Tree Embeddings and Hierarchical Cut Decompositions

10 minute read

Published:

As part of my effort to understand the broader literature surrounding the areas I hope to work on in the future, I am studying both foundational papers and contemporary developments. Alongside my primary focus on the work of James R. Lee, I plan to read a number of folklore and classical papers that have shaped the modern theory of metric embeddings.

metric spaces

Dynamic Approximate Nearest-Neighbor Search in Doubling Metrics

18 minute read

Published:

Well, in this blog post we are going to review several papers and understand the techniques that are utilized in order to tackle several problems related to areas such as nearest neighbor problems, the facility location problem, and so on.

nearest neighbor search

Dynamic Approximate Nearest-Neighbor Search in Doubling Metrics

18 minute read

Published:

Well, in this blog post we are going to review several papers and understand the techniques that are utilized in order to tackle several problems related to areas such as nearest neighbor problems, the facility location problem, and so on.

norms

Lewis Weights, Leverage Scores, and Whitening — Chapter 2

12 minute read

Published:

This is the second chapter in my series on Sparsifying Sums of Norms. Chapter 1 set up the general problem and briefly mentioned Lewis weights. In the second post of this series on sparsification of the norm, I want to turn to the $\ell_p$ row sampling paper. I’ll be spending a few posts on this one, because I think it is genuinely revealing on the subject it is worth pondering carefully and going through in some detail. The paper relies heavily on the works of Milman and Talagrand(for example), so I may cover those seminal papers too at some point. At a high level, this paper is a vast generalization of the Johnson–Lindenstrauss lemma, with a few extremely technical steps, but the overall theme is clear and elegant. I especially like how they used Talagrand’s result and intuition, and the way they brought in Lewis weights to pull everything together.

parallel algorithms

planar graphs

And god said let there be dijkstra

18 minute read

Published:

Alright, in this work I want to explain the seminal work of Jittat Fakcharoenphol and Satish Rao in 2006, devising the algorithm of FR-Dijkstra, which is so insightful and meaningful.

probability

proof complexity

r-division

And god said let there be dijkstra

18 minute read

Published:

Alright, in this work I want to explain the seminal work of Jittat Fakcharoenphol and Satish Rao in 2006, devising the algorithm of FR-Dijkstra, which is so insightful and meaningful.

random graphs

Bukh’s Problem on Coloring Random Subgraphs

5 minute read

Published:

So, assume that we have a graph $G = (V, E)$. By $G_p$ for some $p \in (0,1)$ we mean a subgraph such that the probability of each edge appearing in that subgraph is independent with probability $p$.

shortest paths

And god said let there be dijkstra

18 minute read

Published:

Alright, in this work I want to explain the seminal work of Jittat Fakcharoenphol and Satish Rao in 2006, devising the algorithm of FR-Dijkstra, which is so insightful and meaningful.

sparsification

Lewis Weights, Leverage Scores, and Whitening — Chapter 2

12 minute read

Published:

This is the second chapter in my series on Sparsifying Sums of Norms. Chapter 1 set up the general problem and briefly mentioned Lewis weights. In the second post of this series on sparsification of the norm, I want to turn to the $\ell_p$ row sampling paper. I’ll be spending a few posts on this one, because I think it is genuinely revealing on the subject it is worth pondering carefully and going through in some detail. The paper relies heavily on the works of Milman and Talagrand(for example), so I may cover those seminal papers too at some point. At a high level, this paper is a vast generalization of the Johnson–Lindenstrauss lemma, with a few extremely technical steps, but the overall theme is clear and elegant. I especially like how they used Talagrand’s result and intuition, and the way they brought in Lewis weights to pull everything together.

stochastic processes

sublinear algorithms

tree embeddings

Probabilistic Tree Embeddings and Hierarchical Cut Decompositions

10 minute read

Published:

As part of my effort to understand the broader literature surrounding the areas I hope to work on in the future, I am studying both foundational papers and contemporary developments. Alongside my primary focus on the work of James R. Lee, I plan to read a number of folklore and classical papers that have shaped the modern theory of metric embeddings.