Search Results

Documents authored by Jayram, T. S.

Found 2 Possible Name Variants:

Jayram, T.S.

Document
DOI: 10.4230/OASIcs.SOSA.2018.15
Simple Analyses of the Sparse Johnson-Lindenstrauss Transform

Authors: Michael B. Cohen, T.S. Jayram, and Jelani Nelson

Published in: OASIcs, Volume 61, 1st Symposium on Simplicity in Algorithms (SOSA 2018)

Abstract
For every n-point subset X of Euclidean space and target distortion 1+eps for 0<eps<1, the Sparse Johnson Lindenstrauss Transform (SJLT) of (Kane, Nelson, J. ACM 2014) provides a linear dimensionality-reducing map f:X-->l_2^m where f(x) = Ax for A a matrix with m rows where (1) m = O((log n)/eps^2), and (2) each column of A is sparse, having only O(eps m) non-zero entries. Though the constructions given for such A in (Kane, Nelson, J. ACM 2014) are simple, the analyses are not, employing intricate combinatorial arguments. We here give two simple alternative proofs of their main result, involving no delicate combinatorics. One of these proofs has already been tested pedagogically, requiring slightly under forty minutes by the third author at a casual pace to cover all details in a blackboard course lecture.
Cite as

Michael B. Cohen, T.S. Jayram, and Jelani Nelson. Simple Analyses of the Sparse Johnson-Lindenstrauss Transform. In 1st Symposium on Simplicity in Algorithms (SOSA 2018). Open Access Series in Informatics (OASIcs), Volume 61, pp. 15:1-15:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:OASIcs.SOSA.2018.15,
  author =	{Cohen, Michael B. and Jayram, T.S. and Nelson, Jelani},
  title =	{{Simple Analyses of the Sparse Johnson-Lindenstrauss Transform}},
  booktitle =	{1st Symposium on Simplicity in Algorithms (SOSA 2018)},
  pages =	{15:1--15:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-064-4},
  ISSN =	{2190-6807},
  year =	{2018},
  volume =	{61},
  editor =	{Seidel, Raimund},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2018.15},
  URN =		{urn:nbn:de:0030-drops-83056},
  doi =		{10.4230/OASIcs.SOSA.2018.15},
  annote =	{Keywords: dimensionality reduction, Johnson-Lindenstrauss, Sparse Johnson-Lindenstrauss Transform}
}

Jayram, T. S.

Document
DOI: 10.4230/LIPIcs.ICALP.2017.52
Randomized Communication vs. Partition Number

Authors: Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson

Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)

Abstract
We show that randomized communication complexity can be superlogarithmic in the partition number of the associated communication matrix, and we obtain near-optimal randomized lower bounds for the Clique vs. Independent Set problem. These results strengthen the deterministic lower bounds obtained in prior work (Goos, Pitassi, and Watson, FOCS 2015). One of our main technical contributions states that information complexity when the cost is measured with respect to only 1-inputs (or only 0-inputs) is essentially equivalent to information complexity with respect to all inputs.
Cite as

Mika Göös, T. S. Jayram, Toniann Pitassi, and Thomas Watson. Randomized Communication vs. Partition Number. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.ICALP.2017.52,
  author =	{G\"{o}\"{o}s, Mika and Jayram, T. S. and Pitassi, Toniann and Watson, Thomas},
  title =	{{Randomized Communication vs. Partition Number}},
  booktitle =	{44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)},
  pages =	{52:1--52:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-041-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{80},
  editor =	{Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.52},
  URN =		{urn:nbn:de:0030-drops-74861},
  doi =		{10.4230/LIPIcs.ICALP.2017.52},
  annote =	{Keywords: communication complexity, partition number, information complexity}
}
Document
DOI: 10.4230/LIPIcs.CCC.2016.5
A Composition Theorem for Conical Juntas

Authors: Mika Göös and T. S. Jayram

Published in: LIPIcs, Volume 50, 31st Conference on Computational Complexity (CCC 2016)

Abstract
We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications: - AND-OR trees. We show a near-optimal ~Omega(n^{0.753...}) randomised communication lower bound for the recursive NAND function (a.k.a. AND-OR tree). This answers an open question posed by Beame and Lawry. - Majority trees. We show an Omega(2.59^k) randomised communication lower bound for the 3-majority tree of height k. This improves over the state-of-the-art already in the context of randomised decision tree complexity.
Cite as

Mika Göös and T. S. Jayram. A Composition Theorem for Conical Juntas. In 31st Conference on Computational Complexity (CCC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 50, pp. 5:1-5:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{goos_et_al:LIPIcs.CCC.2016.5,
  author =	{G\"{o}\"{o}s, Mika and Jayram, T. S.},
  title =	{{A Composition Theorem for Conical Juntas}},
  booktitle =	{31st Conference on Computational Complexity (CCC 2016)},
  pages =	{5:1--5:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-008-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{50},
  editor =	{Raz, Ran},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2016.5},
  URN =		{urn:nbn:de:0030-drops-58497},
  doi =		{10.4230/LIPIcs.CCC.2016.5},
  annote =	{Keywords: Composition theorems, conical juntas}
}
Document
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2014.762
Exchangeability and Realizability: De Finetti Theorems on Graphs

Authors: T. S. Jayram and Jan Vondrák

Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)

Abstract
A classic result in probability theory known as de Finetti's theorem states that exchangeable random variables are equivalent to a mixture of distributions where each distribution is determined by an i.i.d. sequence of random variables (an "i.i.d. mix"). Motivated by a recent application and more generally by the relationship of local vs. global correlation in randomized rounding, we study weaker notions of exchangeability that still imply the conclusion of de Finetti's theorem. We say that a bivariate distribution rho is G-realizable for a graph G if there exists a joint distribution of random variables on the vertices such that the marginal distribution on each edge equals rho. We first characterize completely the G-realizable distributions for all symmetric/arc-transitive graphs G. Our main results are forms of de Finetti's theorem for general graphs, based on spectral properties. Let lambda_1(G) >= ... >= lambda_n(G) denote the eigenvalues of the adjacency matrix of G. 1. We prove that if rho is G_n-realizable for a sequence of graphs such that lambda_n(G_n) / lambda_1(G_n) tends to 0, then rho is described by a probability matrix that is positive-semidefinite. For random variables on domains of size |D| <= 4, this implies that rho must be an i.i.d. mix. 2. If rho is G_n-realizable for a sequence of (n,d,lambda)-graphs G_n (d-regular with all eigenvalues except for one bounded by lambda in absolute value) such that lambda(G_n) / d(G_n) tends to 0, then rho is an i.i.d. mix. 3. If rho is G_n-realizable for a sequence of directed graphs such that each of them is an arbitrary orientation of an (n,d,lambda)-graph G_n, and lambda(G_n) / d(G_n) tends to 0, then rho is an i.i.d. mix.
Cite as

T. S. Jayram and Jan Vondrák. Exchangeability and Realizability: De Finetti Theorems on Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 762-778, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jayram_et_al:LIPIcs.APPROX-RANDOM.2014.762,
  author =	{Jayram, T. S. and Vondr\'{a}k, Jan},
  title =	{{Exchangeability and Realizability: De Finetti Theorems on Graphs}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)},
  pages =	{762--778},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-74-3},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{28},
  editor =	{Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.762},
  URN =		{urn:nbn:de:0030-drops-47375},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2014.762},
  annote =	{Keywords: exchangeability, de Finetti’s Theorem, spectral graph theory, regularity lemma}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact