{'fraction_non_alphanumeric': 0.05356991615143559, 'fraction_numerical': 0.021343270940967222, 'mean_word_length': 3.5606411741985324, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 1, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Rounding semidefinite programs for large-domain problems via Brownian motion

We present a new simple method for rounding a semidefinite programming relaxation of a constraint satisfaction problem. We apply it to the problem of approximate angular synchronization. Specifically, we are given directed distances on a circle (i.e., directed angles) between pairs of elements and our goal is to assign the elements to positions on a circle so as to preserve these distances as much as possible. The feasibility of our rounding scheme is based on properties of the well-known stochastic process called Brownian motion. Based on computational and other evidence, we conjecture that this rounding scheme yields an approximation guarantee that is very close to the best-possible guarantee (assuming the Unique-Games Conjecture).


Introduction
We present an alternate approach to the Relaxed Linear Equations mod p (Rel-Lin-Eq) problem studied in [MN11]. Our new approach is also based on rounding a semidefinite programming relaxation but uses a different rounding technique. Based on computational evidence and other justification, we believe this approach has essentially the same approximation guarantee of .854 for Rel-Lin-Eq as proven for a different algorithm presented in [MN11].
We are given a set E of equations in the form of x j − x i ≡ d ij ( mod p). Let X = {x i } be the set of elements and let n = |X |. We assign each element in X a (integral) value from the set [0, p). For a fixed assignment, an equation has value x j − x i ≡ d ij ± y ij (mod p), for y ij ≤ p/2. Since y ij can have a nonnegative value of at most p/2, we divide y ij by p/2 in order to obtain a normalized value between 0 and 1. Our goal is to find an assignment that maximizes the sum ij∈E (1 − 2y ij /s). More precisely, we formulate our objective function as follows.
This problem generalizes the Max-Cut problem: For any edge ij in a graph, we write the constraint x j −x i ≡ p/2( mod p). Then an α-approximation to Rel-Lin-Eq yields an α-approximation for Max-Cut. It can be viewed as an approximate version of the angular synchronization problem studied by Singer [Sin11]. Originally, our motivation was to develop rounding methods for constraint satisfaction problems whose solutions to assignment-constraint based SDPs can have the property that no pair of assignment vectors have a high dot product despite the solution having a high objective value. (e.g., A problem with this property is Maximum Acyclic Subgraph, which has since been proven to be Unique-Games hard to approximate to within a factor greater than Our rounding scheme is based on properties of the well-known stochastic process called Brownian motion. Theoretically, this procedure could be applied to other problems that can be modeled using the standard assignment-constraint based SDP framework (i.e., SDP formulation (P + ) in Section 2.1). However, it does seem tailor-made for our particular objective function. It is also reminiscent of "sticky" random walks used in constructive approaches to discrepancy minimization [Ban10], although these results focus on assigning each element a binary value and one of our main motivations was to study how to approximate large-domain problems.

Organization
After presenting our quadratic formulations and relaxations in Section 2, we present our rounding procedure in Section 3. In Section 4, we discuss Brownian motion and how it relates to our rounding procedure. Then we prove that our rounding procedure is feasible most of the time; precisely, at least .96 of the time, it assigns a (non-random) position to a variable. First, we prove this for a continuous process (Section 5) and then for a discrete process (Section 6). Finally, in Section 7, we state a conjecture regarding the correlation of two random walks, which is supported by extensive computational experiments. A positive resolution to this conjecture would be one way to prove that this rounding procedure has a guarantee close to the best-known guarantee of .854 [MN11] (and close to the best-possible guarantee of .878 under the Unique-Games Conjecture).
This formula for creating such a set F p of vectors can be generalized for any even value of p (where the absolute value of each coordinate of each vector is . We obtain the following quadratic program for Rel-Lin-Eq. Let P denote the set of integers in [0, p).
A Quadratic Program (Q ): For each variable x i ∈ X , the corresponding set of p vectors has the same configuration up to rotation, reflection and translation. This is enforced by Constraints (1) and (3). In an integral solution, the set of p vectors corresponding to variable x i is identical to the set of p vectors corresponding to the variable x j , for all variables x i , x j ∈ X . This follows from the fact that all vectors belong to F p . The only difference is that vectors in the two sets may have different labels (i.e., one set of vectors can be viewed as a rotation of the other set). Then the relative values or positions of two variables only depends on the rotations of the labels. In other words, if for variables x i and x j , the same vectors have the same labels, then the two variables will be assigned to the same position.
j and x i is in position k, x j should be in position k + 3. Given an integral solution, we can determine the position of each variable by picking a vector, and assigning each variable to the label to which that vector corresponds for that variable.

Semidefinite Relaxations
To obtain a semidefinite relaxation of (Q), we remove Constraint (4) and require only that each v k i ∈ Ê pn . Note that even in the semidefinite relaxation, the set of p vectors corresponding to a particular variable x i have the same configuration for each variable up to rotation, reflection and translation. We refer to the set of vectors corresponding to a variable x i as a constellation C i . We show that certain properties hold for each constellation.
A Semidefinite Program (P ): Let v p be a vector in Ê p 2 in which each entry is √ 2 √ p . Let e i ∈ Ê p 2 be the indicator vector which has a 1 in the i th position and 0 elsewhere. For k such that 0 ≤ k ≤ p/2, we define w k as follows: Definition 1. Let the constellation C 0 be the set of s unit vectors {v 0 } is equivalent to the constellation C 0 up to rotation, reflection and translation.
. Without loss of generality, let us assume that v ik = √ 2 √ p e k for 1 ≤ k ≤ p/2. We can assume this since for all k ∈ P , we have (i) ||v ik || = √ 2 √ p (Lemma 2) and (ii) v ij · v ik = 0 for all j, k ∈ P such that j = k (Lemma 3).
k=1 v ik . Thus, there is some rotation of the vectors in C i such that the resulting set of vectors is equivalent to C 0 .
Lemma 2. For all x i ∈ X and k ∈ P , || Proof.
This equals 0 if the intervals [a, b] and [c, d] are non-overlapping, since then d(a, c) Another way to write a semidefinite program is to use a standard formulation based on assignment constraints (e.g., see Quadratic Program (Q 2 ) in [MN11]).
Given a solution for (P + ), we can construct a solution for (P ) as follows.
It is not difficult to see that the transformation in (15) preserves the objective value. In our computational experiments, we used solutions for (P + ), which are more constrained than solutions for (P ) (e.g., Constraint (9) is not implied by the constraints in (P )). However, we feel it is somewhat clearer to present the rounding algorithm in the next section based on a solution for (P ).

Relaxation on an Arbitrarily Large Domain
Note that we can replace p with an arbitrarily large constant s. Suppose s is a multiple of p (i.e., s = ℓp). Then we can scale each constraint so that The optimal objective value of the original and the scaled problem are the same. Moreover, given a solution for (P ) on the domain of size p, we can create a solution for the scaled problem on the domain of size s = ℓp with the same objective value without resolving the relaxation (P ). Thus, we can assume that s is an extremely large constant. We assume this since our rounding algorithms work best on a large domain.

Rounding the Relaxation
Our algorithm for Rel-Lin-Eq is based on rounding a solution for the semidefinite relaxation (P ) presented in Section 2.1. The first issue is, how do we use the constellation of vectors C i to determine the position or value of variable x i ? We will consider the following random process with s steps. Let r ∈ Ê sn be a random vector in which each coordinate is chosen according to the normal Given such a random process, we say that there is an extreme sign change with threshold α between times t and t Our algorithm is based on the observation that in this random process, it is very likely that there is exactly one extreme sign change for the threshold α = 1 (i.e., there do not exist two disjoint intervals that both contain extreme sign changes). This is stated in Theorem 1. If this random process has exactly one extreme sign change, then we say that the process first reaches a threshold α at time Note that these intervals are taken modulo s (i.e., they are intervals on a circle).
Theorem 1. If s is a sufficiently large constant, then with probability at least .96, the random process {v k i · r} with s steps has exactly one extreme sign change with threshold 1.

Rounding Algorithm
Given Theorem 1, we present the following rounding algorithm. (ii) Choose a random vector r ∈ Ê sn where each coordinate r i ∼ N (0, 1) for i ∈ {1, . . . , sn}. For each x i ∈ X, we associate the random walk w i . Each walk w i has the same expected behaviour. This follows from the fact that for each i, there is a rotation matrix such that the set of vectors {v k i } is equal to a canonical set of vectors, as stated in Lemma 1 (i.e., for a fixed vertex i, the pairwise (setwise) relationships of the vectors is exactly prescribed by constraints (2) and (4) of the SDP). We prove Theorem 1 in Section 5. First, we briefly discuss Brownian motion, which we will use in the proof of Theorem 1.
To measure the quality of the solution produced by this rounding algorithm, one must analyze the correlation of two random walks. In Section 7, we state a conjecture regarding this correlation, which is supported by extensive computational experiments.

Brownian Motion
In order to analyze the randomized rounding scheme presented above, we will interpret the sequence of vectors corresponding to any fixed variable, v 1 · r, v 2 · r, . . . , v s · r as a random walk. We will show that this random walk is a discrete sampling of a fundamental continuous stochastic process called Brownian motion. We will then use properties of Brownian motion to prove properties of our discrete walk. For background in Brownian motion, we refer the reader to the textbook [KS88].
A stochastic process W t for 0 ≤ t < ∞ is a Brownian motion if it satisfies the following properties: for all choices of i, j, n.
4. W t has continuous sample paths with probability 1.
Our proofs will rely on two basic properties of Brownian motion: the distributions of hitting times and the Reflection Principle.
The first hitting time for level b, denoted by τ b , is defined to be the first time at which W t takes the value b: τ b = inf {t : W t = b}. τ b is a random variable whose distribution has the density function: Roughly stated, the Reflection Principle is the intuitive property that once a Brownian motion hits a level b, it is equally likely to be above and below the level b in the future. More precisely, it states that if W t is a Brownian motion and τ b its hitting time to b, then the process W ′ t defined by (which is the formula for W t "reflected" about the horizontal line y = b after it hits b) is also a Brownian motion. We will use the reflection principle many times in our calculations.

Mapping Our Process to Brownian Motion
Given a constellation of vectors C i , we can assume by Lemma 1 that the vectors have the following configuration. Each vector in this configuration has dimension s/2. Note that in order to make each vector a unit vector, we can multiply each entry by Suppose that r ∈ N (0, 1) s/2 is a vector such that r = (r 1 , r 2 , . . . r s/2 ). Let a ′ = Define the process w i ′ k as w i ′ k = k i=0 r k . Thus, we have that: Let the vector v k represent the vector v k ′ with each entry multiplied by √ s , and define the process w i k as √ s . Thus, we have that: Note that when v k · r = 1 or −1, it is the case that w i k = a−1 2 and a+1 2 , respectively. If we define W t to be a Brownian motion on the continuous interval [0, 1], then w t is a discretization of this continuous process. In the remainder of the paper, when we refer to a particular process w i k , we will drop the superscript i when it is clear from the context, or when we are just referring to a single process.

Probability of Exactly One Extreme Sign Change
In this section, we we prove Theorem 1. We adopt standard statistical notation and denote density function of a continuous random variable X by Pr[X ∈ dx]. For example, if X ∼ N (0, 1), then Pr[X ∈ dx] = 1 √ 2π e −x 2 /2 dx. (Heuristically, dx denotes a very small region around the value x.) We will furthermore write Pr[X ∈ dx(1)] to denote the density function of X when x takes the specific value of 1.
We compute the probability of an event A conditioned on a random variable X taking value X = x by applying the formula:

Probability of at Least One Sign Change
Suppose Brownian motion W t begins at W 0 = 0 and at t = 1 satisfies W 1 = a. Let H + be the minimum time that W reaches the threshold a/2 + 1/2, and H − be the minimum time that W reaches a/2 − 1/2. Note that H + = τ W 1 /2+1/2 and that H − = τ W 1 /2−1/2 . These hitting times depend on the value of W t at time 1, and are therefore are not stopping times. In order to calculate their distributions, we will first fix a and then calculate the distributions of H + and H − , conditioned on the value of W 1 = a. For our proof, we will find it helpful to generalize our definition of H − and H + as follows. Suppose a Brownian motion satisfies W 1 = a. Define H + i to be the first time that W t finishes hitting the following sequence of barriers: a/2 + 1/2, then a/2 − 1/2, then a/2 + 1/2 and so forth until it has crossed i barriers, alternating between the upper and lower barriers. As an example, H + 3 would be the first time that the path hits a/2 + 1/2 after having first hit a/2 + 1/2, and then a/2− 1/2. Similarly, define H − i to be the first time that W t finishes hitting the sequence of barriers: below a/2 − 1/2, above a/2 + 1/2, and so forth until it has crossed i barriers. Our approach will be to consider the decomposition of the total probability into probabilities conditioned on W 1 = a: and calculate the integral on the right-hand-side.
We break the domain of the integral into three parts.

Case (i): a ≥ 1
In this case, the upper barrier is a/2 + 1/2 ≤ a. The condition W 1 = a implies that W t crosses this barrier with probability 1 (i.e. H + ≤ 1). Therefore,

Case (iii): −1 < a < 1
From an application of the inclusion-exclusion principle, note that:

An example of applying the reflection principle
We now sketch the reasoning behind a standard calculation involving the reflection principle of Brownian motion and apply it to calculating Pr[H + ≤ 1 | W 1 = a] for the case −1 < a < 1. We will use this sort of calculation many times in our proofs. Fix a value of a. Suppose a Brownian motion W t (but not restricted to satisfy W 1 = a) hits the value b = a/2 + 1/2 at time τ b (i.e., By the reflection principle, the random process W ′ t is also a Brownian motion. Now consider the subset of Brownian motions {W t |H + ≤ 1, W 1 = a} (i.e., they satisfy τ a/1+1/2 ≤ 1, W 1 = a). Note that these processes correspond exactly to reflected processes W ′ that satisfy W ′ 1 = 2b − W 1 = 1. Thus, the elements in the set {W t |H + ≤ 1, W 1 = a} correspond exactly to elements in the set {W ′ t |W ′ 1 = 1}. Then For a more rigorous justification of these calculations, see [Cha01]. Similarly, one can show that:

An example applying the reflection principle twice
Note that the event {W t |H + ≤ 1 and H − ≤ 1, W 1 = a} corresponds to processes that either cross above the barrier a/2 + 1/2 then below a/2 − 1/2 or vice versa, i.e. processes that satisfy H + 2 ≤ 1 or H − 2 ≤ 1. Therefore, from the inclusion-exclusion principle we have: In order to calculate Pr[H + 2 ≤ 1 | W 1 = a], we apply the reflection principle twice. First, we reflect W t about the line a/2 + 1/2 when it first hits a/2 + 1/2. Call this reflected process W ′ t . A process W t that hits a/2 + 1/2, then hits a/2 − 1/2, then satisfies W 1 = a will correspond exactly to a reflected process W ′ t that first hits a/2 + 1/2 then hits a/2 + 3/2 then achieves W ′ 1 = 1. Next, we reflect the process W ′ t the first time it hits a/2 + 3/2 about the line a/2 + 3/2; call this new process W ′′ t . It is easy to verify that a process W t (prior to reflection) that hits a/2 + 1/2, then a/2 − 1/2, then achieves W 1 = a will correspond exactly to a reflected process W ′′ t that satisfies W ′′ 1 = 2 + a. Therefore, n order to calculate Pr[H + 2 ≤ 1 | W 1 = a], we apply the reflection principle twice. After the process W t W t first hits a/2 + 1/2 and then hits a/2 − 1/2, we reflect the process W t about the line a/2 − 1/2. Call this reflected process W ′ t . A process W t that hits a/2 + 1/2, then hits a/2 − 1/2, then achieves W 1 = a will be reflected to a process W ′ t that first hits a/2 + 1/2 and then achieves W ′ 1 = −1. Next, we reflect the process W ′ t the first time it hits a/2 + 1/2 about the line a/2 + 1/2; call this new process W ′′ t . It is easy to verify that a process W t (prior to reflection) that hits a/2 + 1/2, then a/2 − 1/2, then achieves W 1 = a will correspond exactly to a twice reflected process W ′′ t that achieves W ′′ 1 = 2 + a. Therefore, Therefore, Similarly, one can show Note that the event [H + 2 ≤ 1 and H − 2 ≤ 1 | W 1 = a] corresponds to the event [H + 3 ≤ 1 or H + 3 ≤ 1]. From the calcuations in Section 5.6, the following bound can be easily derived: Combining these calculations, we arrive at:

Totals
Combining the results of the three cases, we obtain:

Probability of Three or More Sign Changes
In this section, we prove the following Lemma: Since the barriers in H + 3 and H − 3 depend on the value of W 1 , as in the previous section, it will be necessary to decompose the total probability into probabilities conditioned on a = W 1 : We partition the domain of the integral into three cases, and calculate the probabilities in each case using the reflection principle. Brownian motion, W , begins at 0 and after t time steps achieves the value W 1 = a. Then let H + be the minimum time that W finishes reaching the thresholds a/2+1/2, a/2−1/2, a/2+1/2 in that order. (Let H − be the min time that W reaches the thresholds a/2− 1/2, a/2+ 1/2, a/2− 1/2 in that order.) We define another process B t , which is a reflection of the process W t over certain thresholds (depending on the case). There are three cases. In this case, we only need to calculate the probability that H − 3 ≤ 1 occurs, since if H + 3 occurs, then H − 3 must also occur. To obtain W ′ t , the process W t is reflected the first time it hits a/2 + 1/2, then the first time this reflected process hits a/2 + 3/2. Using reasoning similar to Section 5.1.5, it can be shown that if the process W t (prior to reflection) hits a/2 + 1/2, then a/2 − 1/2, then a/2 + 1/2, then satisfies W 1 = a (i.e., it satisfies H + 3 ≤ 1 for fixed a), then it will correspond exactly to a process W ′ t that achieves W ′ 1 = a + 2. Therefore,
5.6 Case (iii): −1 < a < 1 By the inclusion-exclusion principle, we have: First, we calculate Pr[H + 3 ≤ 1 | W 1 = a]. The process W ′ t is obtained by reflecting W t the first time it hits a/2 + 1/2, then the first the reflected process hits a/2 + 3/2, then the first time the twice reflected process hits a/2 + 5/2. If W t (prior to reflection) hits a/2 + 1/2, then a/2 − 1/2, then a/2 + 1/2, then achieves W 1 = a, then it will correspond exactly to a thrice reflected process W ′ t that satisfies W ′ 1 = 3. We want to calculate: We have: Thus, we have:

Now we calculate Pr[H
In this case, the process W ′ t is obtained by reflecting W t the first time it hits a/2 − 1/2, then the first time the reflected process hits a/2 − 3/2, then the first time the twice reflected process hits a/2 − 5/2. A process W t that hits a/2 − 1/2, then a/2 + 1/2, then a/2 − 1/2, then satisfies W 1 = a (i.e., it satisfies H − 3 ≤ 1 for fixed a) will correspond exactly to a thrice reflected process W ′ t that satisfies W ′ 1 = −3. We want to compute: We have: Thus, a naive bound on the probability of three sign changes would be to add expressions (17) and (18): The above bound is an overestimate of the probability, because the event [H − 3 ≤ 1 and H + 3 ≤ 1 | W 1 = a] is contained in both (17)

From Brownian Motion to Discrete Random Walks
The randomized rounding procedure for our algorithm involves a discrete random walk; we have proven Lemmas 4 and 5 for the continuous process, Brownian motion. We show in this section that the discretized random walk of the rounding procedure will also satisfy Lemmas 4 and 5. Suppose W t is a Brownian motion. As we showed earlier, the discretized random walk of s steps, w 1 , . . . , w s , can be modeled as the sequence: w 1 = W 1 , w 2 = W 2/s , w 3 = W 3/s , . . . , w s = W 1 .
First, consider the question of whether Lemma 5 implies that w 1 , . . . , w s also does not touch the sequence of barriers ws 2 + 1 2 , ws 2 − 1 2 , ws 2 + 1 2 before time t = 1. Certainly, if W t does not hit this sequence of barriers, then its discretized version also does not hit these three barriers, since w s = W 1 . Therefore Lemma 5 holds for the discrete random walk as well.
Now consider the question of whether Lemma 4 implies that w 1 , . . . , w s hits either of the barriers ws 2 + 1 2 or ws 2 − 1 2 . Note that if W t hits the barrier b at time τ b , it is not necessarily true that there exists an i such that w i ≥ b, since W t could have hit b at some time between the steps of the discretized walk. Therefore, Lemma 4 cannot be immediately adapted to proving properties of the discretized walk. We now prove that the Lemma is true for the discretized walk when the number of steps is a sufficiently large constant.
Recall that random variables H + and H − were defined as the first times that the Brownian motion W t hits the barrier defined by W 1 2 + 1 2 and W 1 2 − 1 2 , respectively. We slightly strengthen these conditions by defining random variablesH + andH − to be the first times that W t hits the barriers W 1 2 + 1 2 + η and W 1 2 − 1 2 − η, respectively, for some very small constant η. Since η will be chosen to be very small, it will not have a large impact on the distributions ofH + andH − relative to H + and H − . The proof of the following lemma involves the same calculations as in the proof of Lemma 4.
Lemma 6. For η > 0 chosen sufficiently small, We use the above Lemma to prove that if the continuous process W t hits the barrier a 2 + 1 2 + η, then the discrete random walk will hit the barrier a 2 + 1 2 with high probability. The case for the barrier a 2 − 1 2 is similar. Lemma 7. If the number of steps s of the discretized random walk satisfies s ≥ c η 2 for some constant c, then: Pr w ⌈s·τ a 2 + 1 2 +η ⌉ ≥ a 2 + 1 2 | τ a 2 + 1 2 +η ≤ 1 ≥ .997, where W 1 = a and τ a 2 + 1 2 is the time the continuous process hits the barrier a 2 + 1 2 .