Srikanth Srinivasan's
Publications (in reverse chronological order):
- Prasad Chaugule, Mrinal Kumar, Nutan Limaye,
Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan: Schur
Polynomials do not have small formulas if the Determinant doesn't!
Tech. report: ECCC
26:172 (2019) , arXiv:1911.12520
- Srikanth Srinivasan: A Robust Version of
Hegedus's Lemma, with Applications
Conf. version: STOC 2020 (to appear)
Tech. report: ECCC
27:46 (2020)
- Nutan Limaye, Srikanth Srinivasan, Utkarsh
Tripathi: More on AC^0[2] and Variants of the Majority Function
Conf. version: Proceedings
of FSTTCS 2019: 22:1-22:14
Tech. report: ECCC
26:133 (2019)
- Srikanth Srinivasan, Utkarsh Tripathi, S.
Venkitesh: On the Probabilistic Degrees of Symmetric Boolean functions
Conf. version: Proceedings
of FSTTCS 2019: 28:1-28:14
Tech. report: ECCC
26:138 (2019)
- Srikanth Srinivasan, Utkarsh Tripathi, S.
Venkitesh: Decoding Downset Codes Over a Grid
Tech. report: ECCC
26:109 (2019) , arXiv:1908.07215
- Igor Oliveira, Rahul Santhanam, Srikanth
Srinivasan: Parity Helps to Compute Majority
Conf. version: Proceedings
of CCC 2019: 23:1-23:17
Tech.
report: ECCC
26:73 (2019)
- Srikanth Srinivasan: Strongly Exponential
Separation Between Monotone VP and Monotone VNP
Tech. report: ECCC
26:32 (2019) , arXiv:1903.01630
- Swapnam Bajpai, Vaibhav Krishan, Deepanshu Kush,
Nutan Limaye, Srikanth Srinivasan: A #SAT algorithm for Small
Constant-Depth Circuits with PTF gates.
Conf. version: Proceedings
of
ITCS 2019: 8:1-8:20
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 25:162 (2018)
- Nutan Limaye, Karteek Sreenivasiah, Srikanth
Srinivasan, Utkarsh Tripathi, S. Venkitesh: A Fixed-Depth Size-Hierarchy
Theorem for AC^0[2] via the Coin Problem
Conf. version: Proceedings
of STOC 2019: 442-453
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 25: 157 (2018)
- Siddharth Bhandari, Prahladh Harsha, Tulasimohan
Molli, Srikanth Srinivasan: On the Probabilistic Degree of OR over the
Reals.
Conf. version: Proceedings
of
FSTTCS 2018: 5:1-5:12
Tech. report: ECCC
25:
207 (2018) , arXiv:1812.01982
- Suryajith Chillara, Nutan Limaye, Srikanth
Srinivasan: A Quadratic Size-Hierarchy theorem for Small-Depth
Multilinear Formulas.
Conf. version: Proceedings
of
ICALP 2018: 36:1-36:13
- Suryajith Chillara, Christian Engels, Nutan
Limaye, Srikanth Srinivasan: A
Near-Optimal Depth-Hierarchy Theorem for Small-Depth Multilinear
Circuits.
Conf. version: Proceedings
of
FOCS 2018: 934-945
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 25: 62 (2018) , arXiv:1804.02520
- Suryajith Chillara, Nutan Limaye, Srikanth
Srinivasan: Small-depth Multilinear Formula Lower Bounds for
Iterated Matrix Multiplication, with Applications
Conf. version: Proceedings
of
STACS 2018: 21:1 - 21:15
Tech. report: Electronic
Colloquium
of Computational Complexity (ECCC) 24:156 (2017)
Journal version: SIAM
J. Comput. 48-1 (2019),
- Ninad Rajgopal, Rahul Santhanam, Srikanth
Srinivasan: Deterministically Counting Satisfying Assignments for
Constant-Depth Circuits with Parity Gates, with Implications for Lower
Bounds.
(Note: Essentially this result was known to Ryan Williams. Coming soon
(?): a joint version.)
Conf. version: Proceedings
of MFCS 2018: 78:1-78:15
- Mitali Bafna, Srikanth Srinivasan, Madhu Sudan:
Local decoding and testing of polynomials over grids
Conf. version: Proceedings
of
ITCS 2018: 26:1 - 26:14
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 24:138 (2017) , arXiv:1709.06036
- Guillaume Lagarde, Nutan Limaye, Srikanth
Srinivasan: Lower Bounds and PIT for Non-Commutative Arithmetic
circuits with Restricted Parse Trees.
Conf. version: Proceedings
of
MFCS 2017: 41:1 - 41:14
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 24:
77 (2017)
Journal version: Computational
Complexity (2019) 28(3):471-542
- Ben Rossman, Srikanth Srinivasan: Separation of
AC^0[\oplus] formulas and circuits.
Conf. version: Proceedings
of
ICALP 2017: 50:1 - 50:13
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 24:
22 (2017),
arXiv:1702.03625
Journal version: Theory of Computing, to appear.
- Abhishek Bhrushundi, Prahladh Harsha, Srikanth
Srinivasan: On Polynomial Approximations over Z/2^kZ.
Conf. version: Proceedings
of
STACS 2017: 12:1-12:12.
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 24: 13 (2017)
- Prahladh Harsha, Srikanth Srinivasan: Robust
Multiplication-based Tests for Reed-Muller Codes.
Conf. version: Proceedings
of
FSTTCS 2016: 17:1-17:14.
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 23: 204 (2016), arXiv:1612.03086
Journal version: IEEE
Transactions
on Information Theory 65(1): 184-197 (2019)
- Nikhil Balaji, Nutan Limaye, Srikanth Srinivasan: An Almost Cubic
Lower Bound for Sigma Pi Sigma Circuits
Computing a Polynomial in VP
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 23: 143 (2016)
- Prahladh Harsha, Srikanth Srinivasan: On Polynomial Approximations to
AC^0.
Conf. version: Proceedings
of
RANDOM 2016: 32:1-32:14.
Tech report: Electronic
Colloquium
on Computational Complexity (ECCC) 23: 68 (2016)
Journal version: Random
Struct. Algorithms 54(2): 289-303 (2019)
- Ruiwen Chen, Rahul Santhanam, Srikanth
Srinivasan: Average-Case Lower Bounds and Satisfiability Algorithms for
Small Threshold Circuits.
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 22: 191 (2015)
Conf. version: Proceedings
of
CCC 2016: 1:1-1:35.
Journal version: Invited to Special Issue of Theory
of Computing for CCC 2016.
Theory
of Computing 14(9), 2018, 1-55
- Srikanth
Srinivasan: A
Compression Algorithm for AC^0[2] circuits using Certifying
Polynomials.
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 22:
142 (2015)
- Nutan Limaye, Guillaume Malod, Srikanth Srinivasan: Lower bounds for
non-commutative skew
circuits.
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 22: 22 (2015)
Journal version: Theory
of Computing Volume 12 (2016) Article 12 pp 1-38.
- Hervé Fournier, Nutan Limaye, Meena Mahajan,
Srikanth Srinivasan: The Shifted Partial Derivative Complexity of
Elementary Symmetric Polynomials.
Tech. report:
Electronic Colloquium on Computational Complexity (ECCC) 22: 118
(2015)
Conf. version: Proceedings
of
MFCS (2) 2015: 324-335.
Journal version: Theory
of Computing Volume 13 (2017) Article 9 pp. 1-34
- Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma:
Derandomized Graph Product Re-
sults Using the Low Degree Long Code.
Tech. report: arXiv:1411.3517
Conf. version: Proceedings
of
STACS 2015: 275-287.
- Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan: An
Exponential Lower Bound for
Homogeneous Depth Four Arithmetic Formulas.
Tech. report and journal version: Merged with "Superpolynomial lower
bounds for depth-4..." below.
Conf. version: Proceedings
of
FOCS 2014: 61-70.
- Venkatesan Guruswami, Johan Håstad, Prahladh
Harsha, Srikanth Srinivasan, Girish Varma: Superpolylogarithmic
hypergraph coloring hardness via low-degree long codes.
Tech. report: arXiv:1311.7407
, Electronic
Colloquium on Computational Complexity (ECCC) 20: 167 (2013)
Conf. version: Proceedings
of
STOC 2014: 614-623.
Journal version: SIAM
J. Comput. 46-1 (2017),
- Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan:
Superpolynomial lower bounds
for depth-4 homogeneous arithmetic formulas.
Tech. report: Electronic
Colloquium
on Computational Complexity (ECCC) 21: 5 (2014)
Conf. version: Proceedings
of
STOC 2014: 119-127.
Journal version: SIAM
J. Comput., 46(1),
307–335.
- Hervè Fournier, Nutan Limaye, Guillaume Malod, Srikanth Srinivasan:
Lower bounds for depth-4
formulas computing iterated matrix multiplication.
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 20:
100 (2013).
Conf. version: Proceedings
of
STOC 2014: 128-135.
Journal version:
SIAM
J. Comput. 44(5):
1173-1201 (2015)
- Srikanth Srinivasan: On improved degree lower bounds for polynomial
approximation.
Conf. version: Proceedings
of
FSTTCS 2013: 201–212.
- Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A tail bound for read-k
families of functions.
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 19:
51 (2012)
Journal version: Random
Struct. Algorithms 47(1): 99-108 (2015)
- Justin Gilmer, Michael Saks, Srikanth Srinivasan: Composition limits
and separating examples for
some Boolean function complexity measures.
Tech. report: arXiv:1306.0630
Conf. version: Proceedings
of
CCC 2013: 185–196.
Journal version: Combinatorica
36(3):265-311
(2016).
- Swastik Kopparty, Srikanth Srinivasan: Certifying polynomials for
AC^0(parity), with applications.
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 19:
102 (2012)
Conf. version: Proceedings
of
FSTTCS 2012: 36–47.
Journal version: Theory
of Computing 14(12): 1-24 (2018).
- Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan: Optimal Hitting
Sets for Combinatorial
Shapes.
Tech. report: arXiv.1211.3439
Conf. version: Proceedings
of
RANDOM 2012: 423–434.
Journal version: Invited to Special Issue of Theory
of Computing for APPROX/RANDOM 2012.
Theory
of Computing 9:441-470 (2013).
- Dmitry Gavinsky, Shachar Lovett, Srikanth
Srinivasan: Pseudorandom generators for read-once
ACC^0 .
Conf. version: Proceedings
of
CCC 2012: 287–297.
- Paul Beame, Russell Impagliazzo, Srikanth
Srinivasan: Approximating AC^0 by Small Height Decision Trees and a
Deterministic Algorithm for #AC^0 -SAT.
Conf. version: Proceedings
of
CCC 2012: 117–125.
- Rahul Santhanam, Srikanth Srinivasan: On the
Limits of Sparsification.
Tech. report: Electronic
Colloquium on Computational Complexity (ECCC) 18:
131 (2011).
Conf. version: Proceedings
of
ICALP 2012: 774–785.
- Shachar Lovett, Srikanth Srinivasan: Correlation
bounds for poly-size AC^0 circuits with n^{1-o(1)} symmetric gates.
Conf. version: Proceedings
of
RANDOM 2011: 640–651.
- Andreas Krebs, Nutan Limaye, Srikanth Srinivasan: Streaming algorithms
for recognizing nearly
well-parenthesized expressions.
Tech. report: arXiv:1206.0206
Conf. version: Proceedings
of
MFCS 2011: 412–423.
- Steve Chien, Prahladh Harsha, Alistair Sinclair,
Srikanth Srinivasan: Almost settling the hardness of noncommutative
determinant.
Tech. report: arXiv:1101.1169
Conf. version: Proceedings
of
STOC 2011: 499–508.
- Vikraman Arvind, Srikanth Srinivasan: On the Hardness of the
Noncommutative Determinant.
Tech. report: arXiv:0910.2370
Conf. version: Proceedings
of
STOC 2010: 677–686.
Journal version: Compuational
Complexity
27(1): 1-29 (2018)
- Vikraman Arvind, Srikanth Srinivasan: The Remote
Point Problem, Small Bias Spaces, and Expanding Generator Sets.
Tech. report: arXiv:0909.5313
Conf. version: Proceedings
of
STACS 2010: 59–70.
- Vikraman Arvind, Srikanth Srinivasan: Circuit
Lower Bounds, Help Functions, and the Remote Point Problem.
Tech. report: arXiv:0911.4337
Conf. version: Proceedings
of
ICS 2010: 383–397.
- Vikraman Arvind, Pushkar S. Joglekar, Srikanth Srinivasan: Arithmetic
Circuits and the Hadamard
Product of Polynomials.
Tech. report: arXiv:0907.4006
Conf. version: Proceedings
of
FSTTCS 2009: 25–36.
- Vikraman Arvind, Pushkar S. Joglekar, Srikanth
Srinivasan: On Lower Bounds for Constant Width Arithmetic Circuits.
Tech. report: arXiv:0907.3780
Conf. version: Proceedings
of
ISAAC 2009: 637–646.
- Vikraman Arvind, Partha Mukhopadhyay, Srikanth
Srinivasan: New Results on Noncommutative and Commutative Polynomial
Identity Testing.
Tech. report: arXiv:0801:0514.
Conf. version: Proceedings
of
CCC 2008: 268-279.
Journal version: Computational
Complexity 19(4):
521-558 (2010)