query complexity
Query complexity refers to the number of queries a learning algorithm needs to make to achieve a certain level of performance or accuracy. It is an important measure for evaluating the efficiency of algorithms, especially in scenarios with limited access to information.
- Bits Leaked per Query: Information-Theoretic Bounds for Adversarial Attacks on LLMs
- Discovering Data Structures: Nearest Neighbor Search and Beyond
- Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design
- From Counterfactuals to Trees: Competitive Analysis of Model Extraction Attacks
- Near-Optimal Quantum Algorithms for Computing (Coarse) Correlated Equilibria of General-Sum Games
- Price of Parsimony: Complexity of Fourier Sparsity Testing
- Protocols for Verifying Smooth Strategies in Bandits and Games
- Quantum Speedups for Minimax Optimization and Beyond
- Robust Regression of General ReLUs with Queries
- Sampling from multi-modal distributions with polynomial query complexity in fixed dimension via reverse diffusion
- Tight Bounds for Answering Adaptively Chosen Concentrated Queries