- Complexity of Unambiguous Problems in ΣP2
2025/10/21 by Gilboa, Matan, Goldberg, Paul W., Koutsoupias, Elias +1 · 1 citation
#Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.0 #F.2 #FOS: Computer and information sciences
- Scalability Challenges in Variational Quantum Optimization under Stochastic Noise
2025/03/18 by Bärligea, Adelina, Poggel, Benedikt, Lorenz, Jeanette Miriam · 4 citations
#68Q12 #81P68 #90C27 #90C59 #F.1.2 #F.2 #FOS: Physical sciences #G.1.6 #G.3 #Quantum Physics (quant-ph)
- From Independence of Clones to Composition Consistency: A Hierarchy of Barriers to Strategic Nomination
2025/02/24 by Berker, Ratip Emin, Casacuberta, Sílvia, Robinson, Isaac +3 · 1 voice · 3 citations
#68Q25 #68T01 #91B12 #91B14 #Computer Science and Game Theory (cs.GT) #F.2 #FOS: Computer and information sciences #I.2 #J.4
- Adaptive Approximation Schemes for Matching Queues
2025/01/15 by AmaniHamedani, Alireza, Aouad, Ali, Saberi, Amin · 2 citations
#60K25 (Secondary) #68W27 (Primary) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #G.3
- Distributed Model Checking in Graphs Classes of Bounded Expansion
2024/11/22 by Blin, Lélia, Fomin, Fedor V., Fraigniaud, Pierre +5 · 1 citation
#Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences
- Improved Approximations for Stationary Bipartite Matching: Beyond Probabilistic Independence
2024/11/12 by AmaniHamedani, Alireza, Aouad, Ali, Pollner, Tristan +1 · 2 citations
#68W27 #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #G.3
- RPS: A Generic Reservoir Patterns Sampler
2024/10/31 by Diop, Lamine, Plantevit, Marc, Soulet, Arnaud · 1 citation
#60: Probability theory #Artificial Intelligence (cs.AI) #Combinatorics (math.CO) #E.1 #E.2 #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.3 #Machine Learning (cs.LG) #Probability (math.PR)
- A Tight Subexponential-time Algorithm for Two-Page Book Embedding
2024/04/22 by Ganian, Robert, Mueller, Haiko, Ordyniak, Sebastian +2 · 1 citation
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #G.2
- A tight Monte-Carlo algorithm for Steiner Tree parameterized by clique-width
2023/07/26 by Bojikian, Narek, Kratsch, Stefan · 1 citation
#05C85 #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences
- Markov Persuasion Processes with Endogenous Agent Beliefs
2023/07/06 by Iyer, Krishnamurthy, Xu, Haifeng, Zu, You · 1 citation
#60J20 #90C40 #91A28 #Computer Science and Game Theory (cs.GT) #F.2 #FOS: Computer and information sciences #FOS: Economics and business #G.3 #Theoretical Economics (econ.TH)
- From Shapley Value to Model Counting and Back
2023/06/25 by Ahmet Kara, Kara, Ahmet, Dan Olteanu +3 · 4 citations
Computer Science · #Advanced Database Systems and Queries #Bayesian Modeling and Causal Inference #Computational Complexity (cs.CC) #Data Management and Algorithms #Databases (cs.DB) #F.2 #F.4.1 #FOS: Computer and information sciences #H.2 #Logic in Computer Science (cs.LO)
- The Computational Complexity of Single-Player Imperfect-Recall Games
2023/05/28 by Tewolde, Emanuel, Oesterheld, Caspar, Conitzer, Vincent +1 · 3 citations
#68Q17 #68T37 #91A18 #91A35 #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #F.2 #FOS: Computer and information sciences #I.2 #J.4
- Finding and Counting Patterns in Sparse Graphs
2023/01/06 by Balagopal Komarath, Anant Kumar, Komarath, Balagopal +5 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics
- Algorithms approaching the threshold for semi-random planted clique
2022/12/11 by Rares-Darius Buhai, Pravesh K. Kothari, Buhai, Rares-Darius +3 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #Random Matrices and Applications #Stochastic processes and statistical mechanics
- Slicing all Edges of an n-cube Requires n2/3 Hyperplanes
2022/12/06 by Klein, Ohad · 1 citation
#05D05 #52C35 #Combinatorics (math.CO) #F.2 #FOS: Mathematics #G.2.1
- Which arithmetic operations can be performed in constant time in the RAM model with addition?
2022/06/28 by E. Grandjean, Louis Jachiet, Grandjean, Étienne +1 · 2 citations
Computer Science · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.1.1 #F.1.3 #F.2 #FOS: Computer and information sciences #semigroups and automata theory
- On index divisors and monogenity of certain sextic number fields defined by x6+ax5+b
2022/06/11 by Fadil, Lhoussain El, Kchit, Omar · 1 citation
#11R04 #11R21 #11Y40 #F.2 #FOS: Mathematics #Number Theory (math.NT)
- Burning Number for the Points in the Plane
2022/05/10 by Keil, J. Mark, Mondal, Debajyoti, Moradi, Ehsan · 1 citation
#52C15 #68Q25 #Computational Geometry (cs.CG) #Discrete Mathematics (cs.DM) #F.2 #FOS: Computer and information sciences
- Explicit Lower Bounds Against Ω(n)-Rounds of Sum-of-Squares
2022/04/25 by Max Hopkins, Ting-Chun Lin, Hopkins, Max +1 · 1 citation
Computer Science · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #Computational Complexity (cs.CC) #Error Correcting Code Techniques #F.2 #FOS: Computer and information sciences #FOS: Mathematics #Quantum Computing Algorithms and Architecture
- An efficient quantum algorithm for lattice problems achieving subexponential approximation factor
2022/01/31 by Eldar, Lior, Hallgren, Sean · 1 citation
#Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences #FOS: Physical sciences #Quantum Physics (quant-ph)
- Parameterized Convexity Testing
2021/10/25 by Lahiri, Abhiruk, Newman, Ilan, Varma, Nithin · 1 citation
#68W20 #68W25 #Data Structures and Algorithms (cs.DS) #F.2 #FOS: Computer and information sciences
- Tuning Spectral Element Preconditioners for Parallel Scalability on GPUs
2021/10/14 by Malachi Phillips, Phillips, Malachi, Stefan Kerkemeier +3 · 1 citation
Computer Science · Engineering · #35-04 #Advanced Numerical Methods in Computational Mathematics #D.0 #F.2 #FOS: Computer and information sciences #FOS: Mathematics #G.1.3 #G.4 #I.6 #Matrix Theory and Algorithms #Numerical Analysis (math.NA) #Parallel Computing and Optimization Techniques #Performance (cs.PF)
- k-Center Clustering with Outliers in the Sliding-Window Model
2021/09/24 by de Berg, Mark, Monemizadeh, Morteza, Zhong, Yu · 2 citations
#Computational Geometry (cs.CG) #F.2 #FOS: Computer and information sciences
- Monotone Complexity of Spanning Tree Polynomial Re-visited
2021/09/14 by Chattopadhyay, Arkadev, Datta, Rajit, Ghosal, Utsab +1 · 1 citation
#Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences
- The Power of Two Choices in Graphical Allocation
2021/06/10 by Nikhil Bansal, Ohad N. Feldheim, Bansal, Nikhil +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)
- NekRS, a GPU-Accelerated Spectral Element Navier-Stokes Solver
2021/04/12 by Paul Fischer, Stefan Kerkemeier, Fischer, Paul +19 · 10 citations
Computer Science · Engineering · #35-04 #Advanced Numerical Methods in Computational Mathematics #D.0 #Distributed #F.2 #FOS: Computer and information sciences #G.2 #G.4 #I.6 #Parallel #Parallel Computing and Optimization Techniques #Performance (cs.PF) #Spacecraft and Cryogenic Technologies #and Cluster Computing (cs.DC)
- A tight negative example for MMS fair allocations
2021/04/11 by Feige, Uriel, Sapir, Ariel, Tauber, Laliv · 7 citations
#91B32 #Computer Science and Game Theory (cs.GT) #F.2 #FOS: Computer and information sciences
- Learning to Persuade on the Fly: Robustness Against Ignorance
2021/02/19 by Zu, You, Iyer, Krishnamurthy, Xu, Haifeng · 3 citations
#68Q25 #68W27 #91A28 #Computer Science and Game Theory (cs.GT) #F.2 #FOS: Computer and information sciences #FOS: Economics and business #G.3 #Machine Learning (cs.LG) #Theoretical Economics (econ.TH)
- Data Structures Lower Bounds and Popular Conjectures
2021/02/18 by Dvořák, Pavel, Koucký, Michal, Král, Karel +1 · 1 citation
#Computational Complexity (cs.CC) #F.2 #FOS: Computer and information sciences
- Sensitivity Oracles for All-Pairs Mincuts
2020/11/06 by Baswana, Surender, Pandey, Abhyuday · 1 citation
#Data Structures and Algorithms (cs.DS) #E.1 #F.2 #FOS: Computer and information sciences
more