Learning a Hidden Matching
From MaRDI portal
Publication:4651476
DOI10.1137/S0097539702420139zbMath1055.05142MaRDI QIDQ4651476
Noga Alon, Simon Kasif, Richard Beigel, Steven Rudich, Benjamin Sudakov
Publication date: 21 February 2005
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Extremal problems in graph theory (05C35) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20)
Related Items (25)
Exact learning from an honest teacher that answers membership queries ⋮ Tracing a single user ⋮ Learning Boolean halfspaces with small weights from membership queries ⋮ Linear Time Constructions of Some $$d$$-Restriction Problems ⋮ A survey on nonadaptive group testing algorithms through the angle of decoding ⋮ Reconstructing Markov processes from independent and anonymous experiments ⋮ Non-adaptive learning of a hidden hypergraph ⋮ Learning and Verifying Graphs Using Queries with a Focus on Edge Counting ⋮ Learning a hidden graph using \(O(\log n)\)queries per edge ⋮ Almost tight upper bound for finding Fourier coefficients of bounded pseudo-Boolean functions ⋮ Learning a hidden graph ⋮ Reconstruction and verification of chordal graphs with a distance oracle ⋮ An upper bound of the number of tests in pooling designs for the error-tolerant complex model ⋮ An unexpected meeting of four seemingly unrelated problems: graph testing, DNA complex screening, superimposed codes and secure key distribution ⋮ Vector-Matrix-Vector Queries for Solving Linear Algebra, Statistics, and Graph Problems ⋮ Recovering Social Networks from Individual Attributes ⋮ Learning a hidden uniform hypergraph ⋮ Group Testing with Multiple Mutually-Obscuring Positives ⋮ Network construction with subgraph connectivity constraints ⋮ Reconstruction of hidden graphs and threshold group testing ⋮ Optimal query complexity bounds for finding graphs ⋮ Nonadaptive algorithms for threshold group testing ⋮ Reconstructing Weighted Graphs with Minimal Query Complexity ⋮ Unnamed Item ⋮ Non-adaptive Learning of a Hidden Hypergraph
This page was built for publication: Learning a Hidden Matching
