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

Rubinstein, Aviad

  1. Settling the complexity of computing approximate two-player Nash equilibria
    2016/06/14 by Rubinstein, Aviad · 7 citations
    #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
  2. Inapproximability of Nash Equilibrium
    2014/05/13 by Rubinstein, Aviad · 5 citations
    #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
  3. Computing exact minimum cuts without knowing the graph
    2017/11/08 by Rubinstein, Aviad, Schramm, Tselil, Weinberg, S. Matthew · 5 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  4. Beyond matroids: Secretary Problem and Prophet Inequality with general\n constraints
    2016/04/01 by Aviad Rubinstein, Rubinstein, Aviad · 4 citations
    Computer Science · #Optimization and Search Problems #Complexity and Algorithms in Graphs #Advanced Graph Theory Research
  5. An Optimal Approximation for Submodular Maximization under a Matroid Constraint in the Adaptive Complexity Model
    2018/11/07 by Eric Balkanski, Aviad Rubinstein, Balkanski, Eric +3 · 3 citations
    Computer Science · #Complexity and Algorithms in Graphs #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Rough Sets and Fuzzy Logic
  6. Optimal Single-Choice Prophet Inequalities from Samples
    2019/11/18 by Rubinstein, Aviad, Wang, Jack Z., Weinberg, S. Matthew · 3 citations
    #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  7. Settling the complexity of Nash equilibrium in congestion games
    2020/12/08 by Babichenko, Yakov, Rubinstein, Aviad · 3 citations
    #Computational Complexity (cs.CC) #FOS: Computer and information sciences
  8. The Complexity of Fairness through Equilibrium
    2013/12/21 by Othman, Abraham, Papadimitriou, Christos, Rubinstein, Aviad · 2 citations
    #Computer Science and Game Theory (cs.GT) #F.1.3 #F.2 #FOS: Computer and information sciences #J.4
  9. ETH Hardness for Densest-k-Subgraph with Perfect Completeness
    2015/04/30 by Mark Braverman, Braverman, Mark, Young Kun-Ko +5 · 2 citations
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Machine Learning and Data Classification
  10. An Exponential Speedup in Parallel Running Time for Submodular Maximization without Loss in Approximation
    2018/04/17 by Eric Balkanski, Aviad Rubinstein, Balkanski, Eric +3 · 2 citations
    Computer Science · Engineering · #Complexity and Algorithms in Graphs #Cryptography and Data Security #Ferroelectric and Negative Capacitance Devices
  11. Near Optimal Memory-Regret Tradeoff for Online Learning
    2023/03/03 by Peng, Binghui, Rubinstein, Aviad · 3 citations
    #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
  12. Fast swap regret minimization and applications to approximate correlated equilibria
    2023/10/30 by Peng, Binghui, Rubinstein, Aviad · 3 citations
    #Artificial Intelligence (cs.AI) #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Multiagent Systems (cs.MA)
  13. Parallel Sampling via Counting
    2024/08/18 by Anari, Nima, Gao, Ruiquan, Rubinstein, Aviad · 4 citations
    #Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Probability (math.PR)
  14. On Simplex Pivoting Rules and Complexity Theory
    2014/04/12 by Adler, Ilan, Papadimitriou, Christos, Rubinstein, Aviad · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #G.1.6
  15. Honest signaling in zero-sum games is hard, and lying is even harder
    2015/10/16 by Rubinstein, Aviad · 1 citation
    #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  16. Inapproximability of VC Dimension and Littlestone's Dimension
    2017/05/26 by Pasin Manurangsi, Manurangsi, Pasin, Aviad Rubinstein +1 · 1 citation
    Computer Science · #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Machine Learning and Algorithms #Optimization and Search Problems
  17. Combinatorial Prophet Inequalities
    2016/11/02 by Rubinstein, Aviad, Singla, Sahil · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  18. Hardness of Approximate Nearest Neighbor Search
    2018/03/02 by Rubinstein, Aviad · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  19. Constant-factor approximation of near-linear edit distance in near-linear time
    2019/04/10 by Brakensiek, Joshua, Rubinstein, Aviad · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  20. Reducing approximate Longest Common Subsequence to approximate Edit Distance
    2019/04/10 by Rubinstein, Aviad, Song, Zhao · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  21. Tarski's Theorem, Supermodular Games, and the Complexity of Equilibria
    2019/09/07 by Kousha Etessami, Christos Papadimitriou, Etessami, Kousha +5 · 1 citation
    Computer Science · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.CC #cs.GT
  22. Strategizing against No-Regret Learners in First-Price Auctions
    2024/02/13 by Aviad Rubinstein, Rubinstein, Aviad, Junyao Zhao +1 · 2 citations
    Decision Sciences · Business, Management and Accounting · #Auction Theory and Applications #Consumer Market Behavior and Pricing
  23. The Strongish Planted Clique Hypothesis and Its Consequences
    2020/11/11 by Manurangsi, Pasin, Rubinstein, Aviad, Schramm, Tselil · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  24. Budget-Smoothed Analysis for Submodular Maximization
    2021/02/10 by Rubinstein, Aviad, Zhao, Junyao · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  25. Exponential Communication Separations between Notions of Selfishness
    2020/12/29 by Rubinstein, Aviad, Saxena, Raghuvansh R., Thomas, Clayton +2 · 1 citation
    #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #Theoretical Economics (econ.TH)
  26. Hitting the High Notes: Subset Selection for Maximizing Expected Order Statistics
    2020/12/14 by Mehta, Aranyak, Nadav, Uri, Psomas, Alexandros +1 · 1 citation
    #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences
  27. Beyond Worst-Case Budget-Feasible Mechanism Design
    2022/11/16 by Rubinstein, Aviad, Zhao, Junyao · 1 citation
    #Computer Science and Game Theory (cs.GT) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  28. Approximation Algorithms for LCS and LIS with Truly Improved Running Times
    2021/11/20 by Rubinstein, Aviad, Seddighin, Saeed, Song, Zhao +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  29. Fully-dynamic-to-incremental reductions with known deletion order (e.g. sliding window)
    2022/11/09 by Peng, Binghui, Rubinstein, Aviad · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  30. Envy-Free Cake-Cutting for Four Agents
    2023/11/03 by Alexandros Hollender, Hollender, Alexandros, Aviad Rubinstein +1 · 1 voice · 1 citation
    Computer Science · Engineering · #Logic, programming, and type systems #Optimization and Packing Problems #cs.CC #cs.GT #semigroups and automata theory
  31. Practical algorithms and experimentally validated incentives for equilibrium-based fair division (A-CEEI)
    2023/05/19 by Budish, Eric, Gao, Ruiquan, Othman, Abraham +2 · 1 citation
    #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #FOS: Economics and business #General Economics (econ.GN)
  32. Does Preprocessing help in Fast Sequence Comparisons?
    2021/08/20 by Goldenberg, Elazar, Rubinstein, Aviad, Saha, Barna · 1 citation
    #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences
  33. A constant factor approximation for Nash social welfare with subadditive valuations
    2023/09/09 by Shahar Dobzinski, Dobzinski, Shahar, Wenzheng Li +5 · 1 citation
    Engineering · #Transportation and Mobility Innovations
  34. Local Computation Algorithms for Maximum Matching: New Lower Bounds
    2023/11/15 by Behnezhad, Soheil, Roghani, Mohammad, Rubinstein, Aviad · 2 citations
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  35. Approximate Earth Mover's Distance in Truly-Subquadratic Time
    2023/10/30 by Beretta, Lorenzo, Rubinstein, Aviad · 2 citations
    #Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  36. Cardinality constrained submodular maximization for random streams
    2021/11/14 by Liu, Paul, Rubinstein, Aviad, Vondrak, Jan +1 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  37. When Contracts Get Complex: Information-Theoretic Barriers
    2024/03/14 by Paul Dütting, Dütting, Paul, Michal Feldman +5 · 3 citations
    Decision Sciences · Computer Science · #Auction Theory and Applications #Multi-Agent Systems and Negotiation #Computability, Logic, AI Algorithms
  38. The complexity of approximate (coarse) correlated equilibrium for incomplete information games
    2024/06/04 by Binghui Peng, Aviad Rubinstein, Peng, Binghui +1 · 1 citation
    Decision Sciences · Economics, Econometrics and Finance · #Game Theory and Applications #Economic theories and models #Game Theory and Voting Systems
  39. Approximating Maximum Matching Requires Almost Quadratic Time
    2024/06/12 by Soheil Behnezhad, Behnezhad, Soheil, Mohammad Roghani +3 · 2 citations
    Computer Science · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods #Optimization and Search Problems
  40. Maximizing Non-Monotone Submodular Functions over Small Subsets: Beyond 1/2-Approximation
    2022/04/23 by Rubinstein, Aviad, Zhao, Junyao · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
  41. A Bicriterion Concentration Inequality and Prophet Inequalities for k-Fold Matroid Unions
    2024/11/18 by Alon, Noga, Gravin, Nick, Pollner, Tristan +4 · 1 citation
    #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Probability (math.PR)