The maximal number of hits you can export is 250. When you want to export more records please use the 'Create feeds' function.

1.

Aas, Erik

et al.

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

Sjöstrand, Jonas

KTH, School of Engineering Sciences (SCI), Mathematics (Dept.), Mathematics (Div.).

A product formula for the TASEP on a ring2016In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 48, no 2, p. 247-259Article in journal (Refereed)

Abstract [en]

For a random permutation sampled from the stationary distributionof the TASEP on a ring, we show that, conditioned on the event that the rstentries are strictly larger than the last entries, the order of the rst entries isindependent of the order of the last entries. The proof uses multi-line queues asdened by Ferrari and Martin, and the theorem has an enumerative combinatorialinterpretation in that setting.As an application we prove a conjecture of Lam and Williams concerningSchubert factors of the stationary probability of certain states.Finally, we present a conjecture for the case where the small and large entriesare not separated.

We study random graphs, both G(n, p) and G(n, m), with random orientations on the edges. For three fixed distinct vertices s, a, b we study the correlation, in the combined probability space, of the events {a -> s} and {s -> b}. For G(n, p), we prove that there is a p(c) = 1/2 such that for a fixed p < p(c) the correlation is negative for large enough n and for p > p(c) the correlation is positive for large enough n. We conjecture that for a fixed n >= 27 the correlation changes sign three times for three critical values of p. For G(n, m) it is similarly proved that, with p = m/((n)(2)), there is a critical p(c) that is the solution to a certain equation and approximately equal to 0.7993. A lemma, which computes the probability of non existence of any l directed edges in G(n, m), is thought to be of independent interest. We present exact recursions to compute P(a -> s) and P(a -> s, s -> b). We also briefly discuss the corresponding question in the quenched version of the problem.

By the breakthrough work of Hastad [J ACM 48(4) (2001), 798-859], several constraint satisfaction problems are now known to have the following approximation resistance property: Satisfying more clauses than what picking a random assignment would achieve is NP-hard. This is the case for example for Max E3-Sat, Max E3-Lin, and Max E4-Set Splitting. A notable exception to this extreme hardness is constraint satisfaction over two variables (2-CSP); as a corollary of the celebrated Goemans-Williamson algorithm [J ACM 42(6) (1995), 1115-1145], we know that every Boolean 2-CSP has a nontrivial approximation algorithm whose performance ratio is better than that obtained by picking a random assignment to the variables. An intriguing question then is whether this is also the case for 2-CSPs over larger, non-Boolean domains. This question is still open, and is equivalent to whether the generalization of Max 2-SAT to domains of size d, can be approximated to a factor better than (1 - 1/d(2)). In an attempt to make progress towards this question, in this paper we prove, first, that a slight restriction of this problem, namely, a generalization of linear inequations with two variables per constraint, is not approximation resistant, and, second, that the Not-All-Equal Sat problem over domain size d with three variables per constraint, is approximation resistant, for every d greater than or equal to 3. In the Boolean case, Not-All-Equal Sat with three variables per constraint is equivalent to Max 2-SAT and thus has a nontrivial approximation algorithm; for larger domain sizes, Max 2-SAT can be reduced to Not-All-Equal Sat with three variables per constraint. Our approximation algorithm implies that a wide class of 2-CSPs called regular 2-CSPs can all be approximated beyond their random assignment threshold.

Samorodnitsky and Trevisan [STOC 2000, pp. 191-199] proved that there exists, for every positive integer k, a PCP for NP with O(log n) randomness, query complexity 2k + k(2), free bit complexity 2k, completeness 1 - epsilon, and soundness 2(-k2) + epsilon. In this article, we devise a new "outer verifier," based on the layered label cover problem recently introduced by Dinur et al. [STOC 2003, pp. 595-601], and combine it with a new "inner verifier" that uses the query bits more efficiently than earlier verifiers. Our resulting theorem is that there exists, for every integer f >= 2, every positive integer t <= f (f - 1)/2, and every constant epsilon > 0, a PCP for NP with O(log n) randomness, query complexity f + t, free bit complexity f, completeness 1 - epsilon, and soundness 2(-t) + epsilon. As a corollary, there exists, for every integer q >= 3 and every constant epsilon > 0, a q-query PCP for NP with amortized query complexity 1 + root 2/q + epsilon-we also show in this article that combining our outer verifier with any natural candidate for a corresponding inner verifier gives a PCP that is kess query efficient than the one we obtain.

We study non-Boolean PCPs that have perfect completeness and query three positions in the proof. For the case when the proof consists of values from a domain of size d for some integer constant d >= 2, we construct a nonadaptive PCP with perfect completeness and soundness d(-1) + d(-2) + epsilon, for any constant epsilon > 0, and an adaptive PCP with perfect cornpleteness and soundness d(-1) + epsilon, for any constant epsilon > 0. The latter PCP can be converted into a nonadaptive PCP with perfect completeness and soundness d(-1) + epsilon, for any constant epsilon > 0, where four positions are read from the proof. These results match the best known constructions for the case d = 2 and our proof's also show that the particular predicates we use in our PCPs are nonapproximable beyond the random assignment threshold.

KTH, School of Computer Science and Communication (CSC), Numerical Analysis and Computer Science, NADA.

The square lattice shuffle2006In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 29, no 4, p. 466-474Article in journal (Refereed)

Abstract [en]

We show that the operations of permuting columns and rows separately and independently mix a square matrix in constant time.

KTH, Superseded Departments, Numerical Analysis and Computer Science, NADA.

Venkatesh, S.

On the advantage over a random assignment2004In: Random structures & algorithms (Print), ISSN 1042-9832, E-ISSN 1098-2418, Vol. 25, no 2, p. 117-149Article in journal (Refereed)

Abstract [en]

We initiate the study of a new measure of approximation. This measure compares the performance of an approximation algorithm to the random assignment algorithm. This is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. In this paper, we focus on this measure for the optimization problems Max-Lin-2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and Max-k-Lin-2, a special case of the above problem in which each equation has at most k variables. The main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from Fourier analysis and derandomization.

We give a simple analysis of the PCP with low amortized query complexity of Samorodnitsky and Trevisan [16]. The analysis also applies to the linearity testing over finite fields, giving a better estimate of the acceptance probability in terms of the distance of the tested function to the closest linear function.