\begin{algorithm}[H]
    \caption{Reconstruction($\mathcal{P}$)}
    \begin{algorithmic}[1]\label{alg}
    
        \For{$i=1...\ln(n)$}
            \State Sample $u,v $ from $V$ uniformly.
            \State Compute $Est$ on $\{u,v\} \times V$.
            \State Compute $Int(u,v)$.
            \If{ $|Int(u,v)|\geq \frac{n}{2}$}
                \State Compute $Int'(u,v)$.
                \For{$w \in Int'(u,v)$}
                    \State $Emb(w)=Est(u,w)$
                \EndFor
                \State $x_u,x_v \gets $ middle vertices of $Int'(u,v)$.
                \For{$w \not\in Int'(u,v)$}
                 \If{$Est(x_u,w)>Est(x_v,w)$}
                    \State $Emb(w)= Emb(x_u)+Est(x_u,w)$
                 \EndIf
                 \If{$Est(x_u,w)<Est(x_v,w)$}
                    \State $Emb(w)= Emb(x_u)-Est(x_u,w)$
                 \EndIf                 
                \EndFor
                \Return 
            \EndIf
            \State Return $Emb$
        \EndFor
        \State Return FALSE
    \end{algorithmic}
\end{algorithm}

\begin{algorithm}
[H]
\caption{Reconstruction($\mathcal{P}$)}
\begin{algorithmic}[1]
\For{$i=1...\ln(n)$}
\State Sample $u,v $ from $V$ uniformly.
\State Compute $Est$ on $\{u,v\} \times V$.
\State Compute $Int(u,v)$.
\If{ $|Int(u,v)|\geq \frac{n}{2}$}
\State Compute $Int'(u,v)$.
\For{$w \in Int'(u,v)$}
\State $Emb(w)=Est(u,w)$
\EndFor
\State $x_u,x_v \gets $ middle vertices of $Int'(u,v)$.
\For{$w \not\in Int'(u,v)$}
\If{$Est(x_u,w)>Est(x_v,w)$}
\State $Emb(w)= Emb(x_u)+Est(x_u,w)$
\EndIf
\If{$Est(x_u,w)<Est(x_v,w)$}
\State $Emb(w)= Emb(x_u)-Est(x_u,w)$
\EndIf
\EndFor
\Return
\EndIf
\State Return $Emb$
\EndFor
\State Return FALSE
\end{algorithmic}
\end{algorithm}
{
    "title": "determining a points configuration on the line from a subset of the   pairwise distances",
    "id": "2208.13855",
    "abstract": "we investigate rigidity-type problems on the real line and the circle in the non-generic setting. specifically, we consider the problem of uniquely determining the positions of $n$ distinct points $v = {v_1, \\ldots, v_n}$ given a set of mutual distances $\\mathcal{p} \\subseteq {v \\choose 2}$. we establish an extremal result: if $|\\mathcal{p}| = \\omega(n^{3/2})$, then the positions of a large subset $v' \\subseteq v$, where large means $|v'| = \\omega(\\frac{|\\mathcal{p}|}{n})$, can be uniquely determined up to isometry. as a main ingredient in the proof, which may be of independent interest, we show that dense graphs $g=(v,e)$ for which every two non-adjacent vertices have only a few common neighbours must have large cliques.   furthermore, we examine the problem of reconstructing $v$ from a random distance set $\\mathcal{p}$. we establish that if the distance between each pair of points is known independently with probability $p = \\frac{c \\ln(n)}{n}$ for some universal constant $c > 0$, then $v$ can be reconstructed from the distances with high probability. we provide a randomized algorithm with linear expected running time that returns the correct embedding of $v$ to the line with high probability.   since we posted a preliminary version of the paper on arxiv, follow-up works have improved upon our results in the random setting. gir\\~ao, illingworth, michel, powierski, and scott proved a hitting time result for the first moment at which an time at which one can reconstruct $v$ when $\\mathcal{p}$ is revealed using the erd\\\"os--r\\'enyi evolution, our extremal result lies in the heart of their argument. montgomery, nenadov and szab\\'o resolved a conjecture we posed in a previous version and proved that w.h.p a graph sampled from the erd\\\"os--r\\'enyi evolution becomes globally rigid in $\\mathbb{r}$ at the moment it's minimum degree is $2$.",
    "categories": "math.mg math.co math.pr",
    "doi": "",
    "created": "2022-08-29",
    "updated": "2024-01-27",
    "authors": [
        "itai benjamini",
        "elad tzalik"
    ],
    "affiliation": [],
    "url": "https://arxiv.org/abs/2208.13855"
}
{
    "ToxicityFilter": {
        "text_to_toxicity_attributes": {
            "ref.bib": {
                "toxicity_score": 0.009298885,
                "severe_toxicity_score": 0.0009775162,
                "identity_attack_score": 0.0027378413,
                "insult_score": 0.007493876,
                "profanity_score": 0.014361672,
                "threat_score": 0.006977591,
                "sexually_explicit_score": 0.010438959,
                "flirtation_score": 0.20229049
            },
            "main.tex": {
                "toxicity_score": 0.010115679,
                "severe_toxicity_score": 0.0010967255,
                "identity_attack_score": 0.0033298072,
                "insult_score": 0.0072658747,
                "profanity_score": 0.014839902,
                "threat_score": 0.0073789097,
                "sexually_explicit_score": 0.012739069,
                "flirtation_score": 0.25617662
            },
            "main.bbl": {
                "toxicity_score": 0.011874928,
                "severe_toxicity_score": 0.0011348724,
                "identity_attack_score": 0.003866276,
                "insult_score": 0.0075508766,
                "profanity_score": 0.014532468,
                "threat_score": 0.007521313,
                "sexually_explicit_score": 0.010969753,
                "flirtation_score": 0.27629572
            }
        },
        "reason": null
    }
}
{
    "num_done": {
        "figure": 0,
        "algorithm": 2
    }
}
{
    "NonTrivialRenderingFilter": {
        "white_pixels_ratio": 91.80473599164607,
        "hash": "0387c7c1c0c08f1f",
        "most_frequent_color_ratio": 91.80473599164607
    }
}