Navin Goyal

According to our database, Navin Goyal authored at least 64 papers between 2003 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

InversionView: A General-Purpose Method for Reading Information from Neural Activations.

Xinting Huang, Madhur Panwar, Navin Goyal, Michael Hahn

CoRR, 2024

Learning Syntax Without Planting Trees: Understanding When and Why Transformers Generalize Hierarchically.

Kabir Ahuja, Vidhisha Balachandran, Madhur Panwar, Tianxing He, Noah A. Smith, Navin Goyal, Yulia Tsvetkov

CoRR, 2024

In-Context Learning through the Bayesian Prism.

Madhur Panwar, Kabir Ahuja, Navin Goyal

Proceedings of the Twelfth International Conference on Learning Representations, 2024

2023

Guiding Language Models of Code with Global Context using Monitors.

Lakshya A. Agrawal, Aditya Kanade, Navin Goyal, Shuvendu K. Lahiri, Sriram K. Rajamani

CoRR, 2023

A Theory of Emergent In-Context Learning as Implicit Structure Induction.

Michael Hahn, Navin Goyal

CoRR, 2023

Monitor-Guided Decoding of Code LMs with Static Analysis of Repository Context.

Lakshya A. Agrawal, Aditya Kanade, Navin Goyal, Shuvendu K. Lahiri, Sriram K. Rajamani

Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023

2022

Towards a Mathematics Formalisation Assistant using Large Language Models.

Ayush Agrawal, Siddhartha Gadgil, Navin Goyal, Ashvni Narayanan, Anand Tadipatri

CoRR, 2022

Robust identifiability in linear structural equation models of causal inference.

Karthik Abinav Sankararaman, Anand Louis, Navin Goyal

Proceedings of the Uncertainty in Artificial Intelligence, 2022

When Can Transformers Ground and Compose: Insights from Compositional Generalization Benchmarks.

Ankur Sikarwar, Arkil Patel, Navin Goyal

Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, 2022

Learning and Generalization in Overparameterized Normalizing Flows.

Kulin Shah, Amit Deshpande, Navin Goyal

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

Revisiting the Compositional Generalization Abilities of Neural Sequence Models.

Arkil Patel, Satwik Bhattamishra, Phil Blunsom, Navin Goyal

Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), 2022

2021

Analyzing the Nuances of Transformers' Polynomial Simplification Abilities.

Vishesh Agarwal, Somak Aditya, Navin Goyal

CoRR, 2021

Learning and Generalization in RNNs.

Abhishek Panigrahi, Navin Goyal

Proceedings of the Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, 2021

Are NLP Models really able to Solve Simple Math Word Problems?

Arkil Patel, Satwik Bhattamishra, Navin Goyal

Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, 2021

2020

On the Ability of Self-Attention Networks to Recognize Counter Languages.

Satwik Bhattamishra, Kabir Ahuja, Navin Goyal

CoRR, 2020

Effect of Activation Functions on the Training of Overparametrized Neural Nets.

Abhishek Panigrahi, Abhishek Shetty, Navin Goyal

Proceedings of the 8th International Conference on Learning Representations, 2020

On the Ability and Limitations of Transformers to Recognize Formal Languages.

Satwik Bhattamishra, Kabir Ahuja, Navin Goyal

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, 2020

On the Computational Power of Transformers and Its Implications in Sequence Modeling.

Satwik Bhattamishra, Arkil Patel, Navin Goyal

Proceedings of the 24th Conference on Computational Natural Language Learning, 2020

On the Practical Ability of Recurrent Neural Networks to Recognize Hierarchical Languages.

Satwik Bhattamishra, Kabir Ahuja, Navin Goyal

Proceedings of the 28th International Conference on Computational Linguistics, 2020

2019

Better analysis of greedy binary search tree on decomposable sequences.

Navin Goyal, Manoj Gupta

Theor. Comput. Sci., 2019

Non-Gaussianity of Stochastic Gradient Noise.

Abhishek Panigrahi, Raghav Somani, Navin Goyal, Praneeth Netrapalli

CoRR, 2019

Stability of Linear Structural Equation Models of Causal Inference.

Karthik Abinav Sankararaman, Anand Louis, Navin Goyal

Proceedings of the Thirty-Fifth Conference on Uncertainty in Artificial Intelligence, 2019

Non-Gaussian component analysis using entropy methods.

Navin Goyal, Abhishek Shetty

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Sampling and Optimization on Convex Sets in Riemannian Manifolds of Non-Negative Curvature.

Navin Goyal, Abhishek Shetty

Proceedings of the Conference on Learning Theory, 2019

2018

Depth separation and weight-width trade-offs for sigmoidal neural networks.

Amit Deshpande, Navin Goyal, Sushrut Karmalkar

Proceedings of the 6th International Conference on Learning Representations, 2018

2017

Near-Optimal Regret Bounds for Thompson Sampling.

Shipra Agrawal, Navin Goyal

J. ACM, 2017

Heavy-Tailed Analogues of the Covariance Matrix for ICA.

Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, 2017

2016

On Computing Maximal Independent Sets of Hypergraphs in Parallel.

Ioana Oriana Bercea, Navin Goyal, David G. Harris, Aravind Srinivasan

ACM Trans. Parallel Comput., 2016

Non-negative Matrix Factorization under Heavy Noise.

Chiranjib Bhattacharyya, Navin Goyal, Ravindran Kannan, Jagdeep Pani

Proceedings of the 33nd International Conference on Machine Learning, 2016

2015

Query Complexity of Sampling and Small Geometric Partitions.

Navin Goyal, Luis Rademacher, Santosh S. Vempala

Comb. Probab. Comput., 2015

Heavy-Tailed Independent Component Analysis.

Joseph Anderson, Navin Goyal, Anupama Nandi, Luis Rademacher

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014

Lower Bounds for the Average and Smoothed Number of Pareto-Optima.

Tobias Brunsch, Navin Goyal, Luis Rademacher, Heiko Röglin

Theory Comput., 2014

Expanders via Random Spanning Trees.

Alan M. Frieze, Navin Goyal, Luis Rademacher, Santosh S. Vempala

SIAM J. Comput., 2014

Fourier PCA and robust tensor decomposition.

Navin Goyal, Santosh S. Vempala, Ying Xiao

Proceedings of the Symposium on Theory of Computing, 2014

Annotations for Sparse Data Streams.

Amit Chakrabarti, Graham Cormode, Navin Goyal, Justin Thaler

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

The More, the Merrier: the Blessing of Dimensionality for Learning Large Gaussian Mixtures.

Joseph Anderson, Mikhail Belkin, Navin Goyal, Luis Rademacher, James R. Voss

Proceedings of The 27th Conference on Learning Theory, 2014

2013

Deterministic Algorithms for the Lovász Local Lemma.

Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler

SIAM J. Comput., 2013

The VPN Conjecture Is True.

Navin Goyal, Neil Olver, F. Bruce Shepherd

J. ACM, 2013

Fourier PCA.

Navin Goyal, Santosh S. Vempala, Ying Xiao

CoRR, 2013

Ad impression forecasting for sponsored search.

Abhirup Nath, Shibnath Mukherjee, Prateek Jain, Navin Goyal, Srivatsan Laxman

Proceedings of the 22nd International World Wide Web Conference, 2013

Thompson Sampling for Contextual Bandits with Linear Payoffs.

Shipra Agrawal, Navin Goyal

Proceedings of the 30th International Conference on Machine Learning, 2013

Efficient Learning of Simplices.

Joseph Anderson, Navin Goyal, Luis Rademacher

Proceedings of the COLT 2013, 2013

Further Optimal Regret Bounds for Thompson Sampling.

Shipra Agrawal, Navin Goyal

Proceedings of the Sixteenth International Conference on Artificial Intelligence and Statistics, 2013

2012

Analysis of Thompson Sampling for the Multi-armed Bandit Problem.

Shipra Agrawal, Navin Goyal

Proceedings of the COLT 2012, 2012

Efficient learning of simplices

Navin Goyal, Luis Rademacher

CoRR, 2012

Lower Bounds for the Average and Smoothed Number of Pareto Optima.

Navin Goyal, Luis Rademacher

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

2011

On Dynamic Optimality for Binary Search Trees

Navin Goyal, Manoj Gupta

CoRR, 2011

Dynamic vs. Oblivious Routing in Network Design.

Navin Goyal, Neil Olver, F. Bruce Shepherd

Algorithmica, 2011

2010

Rounds vs. Queries Tradeoff in Noisy Computation.

Navin Goyal, Michael E. Saks

Theory Comput., 2010

Satisfiability Thresholds for k-CNF Formula with Bounded Variable Intersections

Karthekeyan Chandrasekaran, Navin Goyal, Bernhard Haeupler

CoRR, 2010

Enhanced flux balance analysis to model metabolic networks.

Nishanth Ulhas Nair, Navin Goyal, Nagasuma R. Chandra

Proceedings of the First ACM International Conference on Bioinformatics and Computational Biology, 2010

2009

Expanders via random spanning trees.

Navin Goyal, Luis Rademacher, Santosh S. Vempala

Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2009

Learning Convex Bodies is Hard.

Luis Rademacher, Navin Goyal

Proceedings of the COLT 2009, 2009

2008

Lower Bounds for the Noisy Broadcast Problem.

Navin Goyal, Guy Kindler, Michael E. Saks

SIAM J. Comput., 2008

Disorder inequality: a combinatorial approach to nearest neighbor search.

Navin Goyal, Yury Lifshits, Hinrich Schütze

Proceedings of the International Conference on Web Search and Web Data Mining, 2008

2007

An Algorithmic Approach to the Identification of Rigid Domains in Proteins.

Vicky Choi, Navin Goyal

Algorithmica, 2007

2006

The Graham-Knowlton Problem Revisited.

Navin Goyal, Sachin Lodha, S. Muthukrishnan

Theory Comput. Syst., 2006

An Efficient Approximation Algorithm for Point Pattern Matching Under Noise.

Vicky Choi, Navin Goyal

Proceedings of the LATIN 2006: Theoretical Informatics, 2006

Lower bounds for circuits with MOD_m gates.

Arkadev Chattopadhyay, Navin Goyal, Pavel Pudlák, Denis Thérien

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

A parallel search game.

Navin Goyal, Michael E. Saks

Random Struct. Algorithms, 2005

Rounds vs queries trade-off in noisy computation.

Navin Goyal, Michael E. Saks

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

A Combinatorial Shape Matching Algorithm for Rigid Protein Docking.

Vicky Choi, Navin Goyal

Proceedings of the Combinatorial Pattern Matching, 15th Annual Symposium, 2004

2003

Optimal Bandwidth Reservation Schedule in Cellular Network.

Samrat Ganguly, B. R. Badrinath, Navin Goyal

Proceedings of the Proceedings IEEE INFOCOM 2003, The 22nd Annual Joint Conference of the IEEE Computer and Communications Societies, San Franciso, CA, USA, March 30, 2003

Optimal Separation of EROW and CROWPRAMs.

Navin Goyal, Michael E. Saks, Srinivasan Venkatesh

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003