Journal: Algorithmica

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