vix.ing · top · new · best · stats · spec

Bansal, Nikhil

  1. Faster Space-Efficient Algorithms for Subset Sum, k-Sum and Related\n Problems
    2016/12/08 by Nikhil Bansal, Shashwat Garg, Bansal, Nikhil +5 · 1 voice · 2 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Optimization and Packing Problems #Computational Geometry and Mesh Generation
  2. Constructive Algorithms for Discrepancy Minimization
    2010/02/11 by Nikhil Bansal, Bansal, Nikhil · 11 citations
    Mathematics · Computer Science · #Mathematical Approximation and Integration #Limits and Structures in Graph Theory #Digital Image Processing Techniques
  3. New Notions and Constructions of Sparsification for Graphs and Hypergraphs
    2019/05/04 by Bansal, Nikhil, Svensson, Ola, Trevisan, Luca · 8 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  4. On-Line Balancing of Random Inputs
    2019/03/16 by Bansal, Nikhil, Spencer, Joel H. · 8 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  5. A Polylogarithmic-Competitive Algorithm for the k-Server Problem
    2011/10/07 by Bansal, Nikhil, Buchbinder, Niv, Madry, Aleksander +2 · 6 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  6. Online Vector Balancing and Geometric Discrepancy
    2019/12/06 by Bansal, Nikhil, Jiang, Haotian, Singla, Sahil +1 · 6 citations
    #Computational Geometry (cs.CG) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  7. k-Forrelation Optimally Separates Quantum and Classical Query Complexity
    2020/08/16 by Bansal, Nikhil, Sinha, Makrand · 5 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
  8. Min-Max Graph Partitioning and Small Set Expansion
    2011/10/19 by Bansal, Nikhil, Feige, Uriel, Krauthgamer, Robert +5 · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  9. Competitive Algorithms for Generalized k-Server in Uniform Metrics
    2017/07/14 by Nikhil Bansal, Bansal, Nikhil, Marek Eliáš +5 · 3 citations
    Computer Science · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  10. Potential-Function Proofs for First-Order Methods
    2017/12/13 by Nikhil Bansal, Bansal, Nikhil, Anupam Gupta +1 · 4 citations
    Computer Science · Decision Sciences · Mathematics · #Advanced Bandit Algorithms Research #Advanced Optimization Algorithms Research #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Optimization and Control (math.OC) #Stochastic Gradient Optimization Techniques
  11. An Algorithm for Komlós Conjecture Matching Banaszczyk's bound
    2016/05/10 by Nikhil Bansal, Bansal, Nikhil, Daniel Dadush +3 · 4 citations
    Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #Digital Image Processing Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Mathematical Approximation and Integration
  12. Balanced Allocations: The Heavily Loaded Case with Deletions
    2022/05/13 by Nikhil Bansal, Bansal, Nikhil, William Kuszmaul +1 · 4 citations
    Computer Science · Decision Sciences · Economics, Econometrics and Finance · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Game Theory and Voting Systems
  13. Prefix Discrepancy, Smoothed Analysis, and Combinatorial Vector Balancing
    2021/11/13 by Bansal, Nikhil, Jiang, Haotian, Meka, Raghu +2 · 3 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)
  14. Flow Time Scheduling and Prefix Beck-Fiala
    2022/02/04 by Bansal, Nikhil, Rohwedder, Lars, Svensson, Ola · 4 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  15. Algorithmic Discrepancy Beyond Partial Coloring
    2016/11/06 by Bansal, Nikhil, Garg, Shashwat · 3 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  16. Weighted k-Server Bounds via Combinatorial Dichotomies
    2017/04/11 by Nikhil Bansal, Bansal, Nikhil, Marek Eliáš +3 · 2 citations
    Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Auction Theory and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  17. The Gram-Schmidt Walk: A Cure for the Banaszczyk Blues
    2017/08/03 by Bansal, Nikhil, Dadush, Daniel, Garg, Shashwat +1 · 3 citations
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  18. On the discrepancy of random low degree set systems
    2018/10/08 by Bansal, Nikhil, Meka, Raghu · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  19. Resolving Matrix Spencer Conjecture Up to Poly-logarithmic Rank
    2022/08/24 by Nikhil Bansal, Bansal, Nikhil, Haotian Jiang +3 · 3 citations
    Engineering · Mathematics · #Advanced Algebra and Geometry #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Random Matrices and Applications #graph theory and CDMA systems
  20. Smoothed Analysis of the Komlós Conjecture
    2022/04/25 by Nikhil Bansal, Haotian Jiang, Bansal, Nikhil +7 · 2 citations
    Mathematics · #Markov Chains and Monte Carlo Methods #Random Matrices and Applications #Statistical Methods and Inference
  21. A Unified Approach to Discrepancy Minimization
    2022/05/02 by Bansal, Nikhil, Laddha, Aditi, Vempala, Santosh S. · 3 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  22. The Geometry of Scheduling
    2010/08/28 by Bansal, Nikhil, Pruhs, Kirk · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  23. When LP is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings
    2010/08/31 by Nikhil Bansal, Anupam Gupta, Bansal, Nikhil +9 · 1 citation
    Computer Science · Decision Sciences · #Auction Theory and Applications #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Optimization and Search Problems
  24. Minimizing Flow-Time on Unrelated Machines
    2014/01/28 by Bansal, Nikhil, Kulkarni, Janardhan · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  25. Approximation-Friendly Discrepancy Rounding
    2015/12/07 by Nikhil Bansal, Bansal, Nikhil, Viswanath Nagarajan +1 · 1 citation
    Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Mathematical Approximation and Integration
  26. Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines
    2015/11/24 by Bansal, Nikhil, Srinivasan, Aravind, Svensson, Ola · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  27. Nested Convex Bodies are Chaseable
    2017/07/18 by Bansal, Nikhil, Böhm, Martin, Eliáš, Marek +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  28. The Power of Two Choices in Graphical Allocation
    2021/06/10 by Nikhil Bansal, Bansal, Nikhil, Ohad N. Feldheim +1 · 1 citation
    Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · #60C05 #Discrete Mathematics (cs.DM) #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.2 #Genome Rearrangement Algorithms #Optimization and Packing Problems #Optimization and Search Problems #Probability (math.PR)
  29. Online Discrepancy Minimization for Stochastic Arrivals
    2020/07/21 by Bansal, Nikhil, Jiang, Haotian, Meka, Raghu +2 · 1 citation
    #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  30. Learning-Augmented Weighted Paging
    2020/11/18 by Bansal, Nikhil, Coester, Christian, Kumar, Ravi +2 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  31. Pseudorandom density matrices
    2024/07/16 by Bansal, Nikhil, Mok, Wai-Keong, Bharti, Kishor +2 · 2 citations
    #Computational Complexity (cs.CC) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
  32. Quasi-Monte Carlo Beyond Hardy-Krause
    2024/08/12 by Nikhil Bansal, Haotian Jiang, Bansal, Nikhil +1 · 4 citations
    Mathematics · #Mathematical Approximation and Integration #Markov Chains and Monte Carlo Methods
  33. Improved Approximations for Min Sum Vertex Cover and Generalized Min Sum Set Cover
    2020/07/17 by Bansal, Nikhil, Batra, Jatin, Farhadi, Majid +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences
  34. Sensitivity Sampling for k-Means: Worst Case and Stability Optimal Coreset Bounds
    2024/05/02 by Nikhil Bansal, Bansal, Nikhil, Vincent Cohen-Addad +7 · 1 citation
    Computer Science · Engineering · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Face and Expression Recognition #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques
  35. An Improved Bound for the Beck-Fiala Conjecture
    2025/08/03 by Bansal, Nikhil, Jiang, Haotian · 4 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
  36. Decoupling via Affine Spectral-Independence: Beck-Fiala and Komlós Bounds Beyond Banaszczyk
    2025/08/05 by Bansal, Nikhil, Jiang, Haotian · 3 citations
    #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)