Tham gia Đăng nhập
Điểm:3
BlackHat18 avatar Crypto

Đối số lai mà không có khả năng lấy mẫu hiệu quả

lá cờ sy
BlackHat18

Hãy nói rằng tôi có $k$ phân phối, ở đâu $k$ là đa thức lớn, $D_1, D_2, \ldots, D_k$ sao cho mỗi $D_i$ không thể phân biệt về mặt tính toán với phân phối đồng đều.

Có đúng là sự phân phối $D_1 D_2 \ldots D_k$ cũng không thể phân biệt được về mặt tính toán với $k$ bản sao của phân phối thống nhất?

Điều này không đáng kể nếu mỗi $D_i$ có thể lấy mẫu một cách hiệu quả. Nhưng hãy nói rằng họ không phải vậy.

Liệu thực tế có còn đúng không, bằng một cách thông minh nào đó để bỏ qua yêu cầu về khả năng lấy mẫu?

46
1 + 0
Điểm:3
Yehuda Lindell avatar Crypto
lá cờ us
Yehuda Lindell

Đây là một câu hỏi rất thú vị. Tôi nhìn xung quanh và tìm thấy một tờ giấy gọi là Tính toán không thể phân biệt: Một hệ thống phân cấp mẫu bởi Goldreich và Sudan. Điều này chứa một bằng chứng rằng nó không giữ.

0 + 2
BlackHat18 avatar
lá cờ sy
BlackHat18
Chỉ cần làm rõ. Bài báo này nói về hai bản phân phối và cài đặt khi chúng tôi được cung cấp $k$ mẫu từ bất kỳ một bản phân phối nào trong số hai bản phân phối.Tuy nhiên, ở đây, chúng ta hoặc được cung cấp một mẫu từ mỗi $k$ phân phối khác nhau (mỗi mẫu không thể phân biệt bằng tính toán với đồng nhất) hoặc chúng ta được cung cấp $k$ mẫu từ phân phối đồng nhất. Bạn có nghĩ rằng các kỹ thuật hoạt động cho cài đặt đầu tiên (của bài báo) cũng hoạt động cho cài đặt thứ hai (của câu hỏi của tôi) không?
0
Hồi đáp
Yehuda Lindell avatar
lá cờ us
Yehuda Lindell
Ngoài ra còn có các tài liệu tham khảo trong bài báo về công việc trước đây liên quan đến câu hỏi cơ bản hơn. Trực giác của tôi nói rằng điều này sẽ chuyển thành các cài đặt tương tự, nhưng tất nhiên trực giác luôn cần được kiểm tra.
0
Hồi đáp
lá cờ VietNam
Phan Văn Trường
Câu hỏi này là trong các ngôn ngữ khác:

Đăng câu trả lời

Hầu hết mọi người không hiểu rằng việc đặt nhiều câu hỏi sẽ mở ra cơ hội học hỏi và cải thiện mối quan hệ giữa các cá nhân. Ví dụ, trong các nghiên cứu của Alison, mặc dù mọi người có thể nhớ chính xác có bao nhiêu câu hỏi đã được đặt ra trong các cuộc trò chuyện của họ, nhưng họ không trực giác nhận ra mối liên hệ giữa câu hỏi và sự yêu thích. Qua bốn nghiên cứu, trong đó những người tham gia tự tham gia vào các cuộc trò chuyện hoặc đọc bản ghi lại các cuộc trò chuyện của người khác, mọi người có xu hướng không nhận ra rằng việc đặt câu hỏi sẽ ảnh hưởng—hoặc đã ảnh hưởng—mức độ thân thiện giữa những người đối thoại.