Metric Decompositions of Path-Separable Graphs
A prominent tool in many problems involving metric spaces is a notion of randomized...
Multivariate Complexity Analysis of Geometric RED BLUE SET COVER
We investigate the parameterized complexity of Generalized Red Blue Set Cover (...
Secluded Connectivity Problems
Consider a setting where possibly sensitive information sent over a path in a network...
Exact Sampling Algorithms for Latin Squares and Sudoku Matrices via Probabilistic Divide-and-Conquer
We provide several algorithms for the exact, uniform random sampling of Latin squares...
Decision Trees for Function Evaluation: Simultaneous Optimization of Worst and Expected Cost
In several applications of automatic diagnosis and active learning, a central problem...
When Patrolmen Become Corrupted: Monitoring a Graph Using Faulty Mobile Robots
A team of k mobile robots is deployed on a weighted graph whose edge weights represent...
Quantum Algorithm for Triangle Finding in Sparse Graphs
This paper presents a quantum algorithm for triangle finding over sparse graphs that...
String Powers in Trees
In this paper we consider substrings of an unrooted edge‐labeled tree, which...
On the Approximability of the Minimum Rainbow Subgraph Problem and Other Related Problems
In this paper, we study the approximability of the minimum rainbow subgraph (MRS)...
A Framework for Space-Efficient String Kernels
String kernels are typically used to compare genome‐scale sequences whose...
Partial Sorting Problem on Evolving Data
In this paper we investigate the top‐ k ‐selection problem, i.e. to...
On the Information Ratio of Non-perfect Secret Sharing Schemes
A secret sharing scheme is non‐perfect if some subsets of players that cannot...
On Virtual Grey Box Obfuscation for General Circuits
An obfuscator O is Virtual Grey Box (VGB) for a class C of circuits if, for any C...
On the Impossibility of Cryptography with Tamperable Randomness
We initiate a study of the security of cryptographic primitives in the presence of...
Scalable Zero Knowledge Via Cycles of Elliptic Curves
Non‐interactive zero‐knowledge proofs of knowledge for general NP...
How to Eat Your Entropy and Have it Too: Optimal Recovery Strategies for Compromised RNGs
Random number generators (RNGs) play a crucial role in many cryptographic schemes and...
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation
In this work, we show how to use indistinguishability obfuscation to build multiparty...
Self-Bilinear Map on Unknown Order Groups from Indistinguishability Obfuscation and Its Applications
A self‐bilinear map is a bilinear map where the domain and target groups are...
On the Implausibility of Differing-Inputs Obfuscation and Extractable Witness Encryption with Auxiliary Input
The notion of differing‐inputs obfuscation (diO) was introduced by Barak et al....
Combinatorial RNA Design: Designability and Structure-Approximating Algorithm in Watson‐Crick and Nussinov‐Jacobson Energy Models
We consider the Combinatorial RNA Design problem , a minimal instance of RNA design...
Trading Off Worst and Expected Cost in Decision Tree Problems
We characterize the best possible trade‐off achievable when optimizing the...
Efficient Computation of Substring Equivalence Classes with Suffix Arrays
This paper considers enumeration of substring equivalence classes introduced by Blumer...
General Caching Is Hard: Even with Small Pages
Caching (also known as paging ) is a classical problem concerning page replacement...
Convex Hulls Under Uncertainty
We study the convex‐hull problem in a probabilistic setting, motivated by the...
Papers per page: