Search Results

Documents authored by Agrawal, Manindra

Document
DOI: 10.4230/LIPIcs.MFCS.2016.6
Integer Factoring Using Small Algebraic Dependencies

Authors: Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
Integer factoring is a curious number theory problem with wide applications in complexity and cryptography. The best known algorithm to factor a number n takes time, roughly, exp(2*log^{1/3}(n)*log^{2/3}(log(n))) (number field sieve, 1989). One basic idea used is to find two squares, possibly in a number field, that are congruent modulo n. Several variants of this idea have been utilized to get other factoring algorithms in the last century. In this work we intend to explore new ideas towards integer factoring. In particular, we adapt the AKS primality test (2004) ideas for integer factoring. In the motivating case of semiprimes n=pq, i.e. p<q are primes, we exploit the difference in the two Frobenius morphisms (one over F_p and the other over F_q) to factor n in special cases. Specifically, our algorithm is polynomial time (on number theoretic conjectures) if we know a small algebraic dependence between p,q. We discuss families of n where our algorithm is significantly faster than the algorithms based on known techniques.
Cite as

Manindra Agrawal, Nitin Saxena, and Shubham Sahai Srivastava. Integer Factoring Using Small Algebraic Dependencies. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.MFCS.2016.6,
  author =	{Agrawal, Manindra and Saxena, Nitin and Srivastava, Shubham Sahai},
  title =	{{Integer Factoring Using Small Algebraic Dependencies}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{6:1--6:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.6},
  URN =		{urn:nbn:de:0030-drops-64234},
  doi =		{10.4230/LIPIcs.MFCS.2016.6},
  annote =	{Keywords: integer, factorization, factoring integers, algebraic dependence, dependencies}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2015.221
Dimension, Pseudorandomness and Extraction of Pseudorandomness

Authors: Manindra Agrawal, Diptarka Chakraborty, Debarati Das, and Satyadev Nandakumar

Published in: LIPIcs, Volume 45, 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)

Abstract
In this paper we propose a quantification of distributions on a set of strings, in terms of how close to pseudorandom a distribution is. The quantification is an adaptation of the theory of dimension of sets of infinite sequences introduced by Lutz. Adapting Hitchcock's work, we also show that the logarithmic loss incurred by a predictor on a distribution is quantitatively equivalent to the notion of dimension we define. Roughly, this captures the equivalence between pseudorandomness defined via indistinguishability and via unpredictability. Later we show some natural properties of our notion of dimension. We also do a comparative study among our proposed notion of dimension and two well known notions of computational analogue of entropy, namely HILL-type pseudo min-entropy and next-bit pseudo Shannon entropy. Further, we apply our quantification to the following problem. If we know that the dimension of a distribution on the set of n-length strings is s in (0,1], can we extract out O(sn) pseudorandom bits out of the distribution? We show that to construct such extractor, one need at least Omega(log n) bits of pure randomness. However, it is still open to do the same using O(log n) random bits. We show that deterministic extraction is possible in a special case - analogous to the bit-fixing sources introduced by Chor et al., which we term nonpseudorandom bit-fixing source. We adapt the techniques of Gabizon, Raz and Shaltiel to construct a deterministic pseudorandom extractor for this source. By the end, we make a little progress towards P vs. BPP problem by showing that existence of optimal stretching function that stretches O(log n) input bits to produce n output bits such that output distribution has dimension s in (0,1], implies P=BPP.
Cite as

Manindra Agrawal, Diptarka Chakraborty, Debarati Das, and Satyadev Nandakumar. Dimension, Pseudorandomness and Extraction of Pseudorandomness. In 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 45, pp. 221-235, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:LIPIcs.FSTTCS.2015.221,
  author =	{Agrawal, Manindra and Chakraborty, Diptarka and Das, Debarati and Nandakumar, Satyadev},
  title =	{{Dimension, Pseudorandomness and Extraction of Pseudorandomness}},
  booktitle =	{35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015)},
  pages =	{221--235},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-97-2},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{45},
  editor =	{Harsha, Prahladh and Ramalingam, G.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2015.221},
  URN =		{urn:nbn:de:0030-drops-56184},
  doi =		{10.4230/LIPIcs.FSTTCS.2015.221},
  annote =	{Keywords: Pseudorandomness, Dimension, Martingale, Unpredictability, Pseudoentropy, Pseudorandom Extractor, Hard Function}
}
Document
DOI: 10.4230/DagRep.4.9.85
Algebra in Computational Complexity (Dagstuhl Seminar 14391)

Authors: Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Reports, Volume 4, Issue 9 (2015)

Abstract
At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove things about these combinatorial objects is by establishing a connection to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The Razborov-Smolensky polynomial-approximation method for proving constant-depth circuit lower bounds, the PCP characterization of NP, and the Agrawal-Kayal-Saxena polynomial-time primality test are some of the most prominent examples. The algebraic theme continues in some of the most exciting recent progress in computational complexity. There have been significant recent advances in algebraic circuit lower bounds, and the so-called "chasm at depth 4" suggests that the restricted models now being considered are not so far from ones that would lead to a general result. There have been similar successes concerning the related problems of polynomial identity testing and circuit reconstruction in the algebraic model, and these are tied to central questions regarding the power of randomness in computation. Representation theory has emerged as an important tool in three separate lines of work: the "Geometric Complexity Theory" approach to P vs. NP and circuit lower bounds, the effort to resolve the complexity of matrix multiplication, and a framework for constructing locally testable codes. Coding theory has seen several algebraic innovations in recent years, including multiplicity codes, and new lower bounds. This seminar brought together researchers who are using a diverse array of algebraic methods in a variety of settings. It plays an important role in educating a diverse community about the latest new techniques, spurring further progress.
Cite as

Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, and Christopher Umans. Algebra in Computational Complexity (Dagstuhl Seminar 14391). In Dagstuhl Reports, Volume 4, Issue 9, pp. 85-105, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.4.9.85,
  author =	{Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher},
  title =	{{Algebra in Computational Complexity (Dagstuhl Seminar 14391)}},
  pages =	{85--105},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{4},
  number =	{9},
  editor =	{Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas and Umans, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.4.9.85},
  URN =		{urn:nbn:de:0030-drops-48851},
  doi =		{10.4230/DagRep.4.9.85},
  annote =	{Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits}
}
Document
DOI: 10.4230/DagRep.2.10.60
Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)

Authors: Manindra Agrawal, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Reports, Volume 2, Issue 10 (2013)

Abstract
At its core, much of Computational Complexity is concerned with combinatorial objects and structures. But it has often proven true that the best way to prove things about these combinatorial objects is by establishing a connection (perhaps approximate) to a more well-behaved algebraic setting. Indeed, many of the deepest and most powerful results in Computational Complexity rely on algebraic proof techniques. The PCP characterization of NP and the Agrawal-Kayal-Saxena polynomial-time primality test are two prominent examples. Recently, there have been some works going in the opposite direction, giving alternative combinatorial proofs for results that were originally proved algebraically. These alternative proofs can yield important improvements because they are closer to the underlying problems and avoid the losses in passing to the algebraic setting. A prominent example is Dinur's proof of the PCP Theorem via gap amplification which yielded short PCPs with only a polylogarithmic length blowup (which had been the focus of significant research effort up to that point). We see here (and in a number of recent works) an exciting interplay between algebraic and combinatorial techniques. This seminar aims to capitalize on recent progress and bring together researchers who are using a diverse array of algebraic and combinatorial methods in a variety of settings.
Cite as

Manindra Agrawal, Thomas Thierauf, and Christopher Umans. Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). In Dagstuhl Reports, Volume 2, Issue 10, pp. 60-78, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Article{agrawal_et_al:DagRep.2.10.60,
  author =	{Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher},
  title =	{{Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421)}},
  pages =	{60--78},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2013},
  volume =	{2},
  number =	{10},
  editor =	{Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.2.10.60},
  URN =		{urn:nbn:de:0030-drops-39034},
  doi =		{10.4230/DagRep.2.10.60},
  annote =	{Keywords: Computational Complexity, lower bounds, approximazation, pseudo-randomness, derandomization, circuits}
}
Document
DOI: 10.4230/DagSemProc.09421.1
09421 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Abstract
From 11.10. to 16.10.2009, the Dagstuhl Seminar 09421 ``Algebraic Methods in Computational Complexity '' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.1,
  author =	{Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher},
  title =	{{09421 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--22},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.1},
  URN =		{urn:nbn:de:0030-drops-24181},
  doi =		{10.4230/DagSemProc.09421.1},
  annote =	{Keywords: Computational Complexity, Algebra}
}
Document
DOI: 10.4230/DagSemProc.09421.2
09421 Executive Summary – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans

Published in: Dagstuhl Seminar Proceedings, Volume 9421, Algebraic Methods in Computational Complexity (2010)

Abstract
The seminar brought together more than 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for theoretical computer science. We had almost 30 talks, most of them about 40 minutes leaving ample room for discussions. We also had a much appreciated open problem session. The talks ranged over a broad assortment of subjects with the underlying theme of using algebraic techniques. It was very fruitful and has hopefully initiated new directions in research. Several participants specifically mentioned that they appreciated the particular focus on a common class of techniques (rather than end results) as a unifying theme of the workshop. We look forward to our next meeting!
Cite as

Manindra Agrawal, Lance Fortnow, Thomas Thierauf, and Christopher Umans. 09421 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 9421, pp. 1-4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.09421.2,
  author =	{Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas and Umans, Christopher},
  title =	{{09421 Executive Summary – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--4},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9421},
  editor =	{Manindra Agrawal and Lance Fortnow and Thomas Thierauf and Christopher Umans},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09421.2},
  URN =		{urn:nbn:de:0030-drops-24100},
  doi =		{10.4230/DagSemProc.09421.2},
  annote =	{Keywords: Computational Complexity, Algebra}
}
Document
DOI: 10.4230/DagSemProc.07411.1
07411 Abstracts Collection – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
From 07.10. to 12.10., the Dagstuhl Seminar 07411 ``Algebraic Methods in Computational Complexity'' was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.
Cite as

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Abstracts Collection – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.1,
  author =	{Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{07411 Abstracts Collection – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--13},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.1},
  URN =		{urn:nbn:de:0030-drops-13072},
  doi =		{10.4230/DagSemProc.07411.1},
  annote =	{Keywords: Computational complexity, algebra, quantum computing, (de-) randomization}
}
Document
DOI: 10.4230/DagSemProc.07411.2
07411 Executive Summary – Algebraic Methods in Computational Complexity

Authors: Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf

Published in: Dagstuhl Seminar Proceedings, Volume 7411, Algebraic Methods in Computational Complexity (2008)

Abstract
The seminar brought together almost 50 researchers covering a wide spectrum of complexity theory. The focus on algebraic methods showed once again the great importance of algebraic techniques for theoretical computer science. We had almost 30 talks of length between 15 and 45 minutes. This left enough room for discussions. We had an open problem session that was very much appreciated.
Cite as

Manindra Agrawal, Harry Buhrman, Lance Fortnow, and Thomas Thierauf. 07411 Executive Summary – Algebraic Methods in Computational Complexity. In Algebraic Methods in Computational Complexity. Dagstuhl Seminar Proceedings, Volume 7411, pp. 1-3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{agrawal_et_al:DagSemProc.07411.2,
  author =	{Agrawal, Manindra and Buhrman, Harry and Fortnow, Lance and Thierauf, Thomas},
  title =	{{07411 Executive Summary – Algebraic Methods in Computational Complexity}},
  booktitle =	{Algebraic Methods in Computational Complexity},
  pages =	{1--3},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2008},
  volume =	{7411},
  editor =	{Manindra Agrawal and Harry Buhrman and Lance Fortnow and Thomas Thierauf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.07411.2},
  URN =		{urn:nbn:de:0030-drops-13061},
  doi =		{10.4230/DagSemProc.07411.2},
  annote =	{Keywords: Computational complexity, algebra, quantum computing, (de-) randomization}
}
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 Imprint Privacy Contact