Có ai biết về một bài báo phân tích chính thức phiên bản "kém thông minh" của FRI, trong đó các truy vấn được chọn độc lập ở mỗi lớp không? (Đánh đổi với 2x độ dài chứng minh).

cụ thể hai ví dụ mà bạn đưa ra về một kết quả xấu không phải là vấn đề, tôi nghĩ - tức là bạn chỉ cần fri để phát hiện xem bạn *bắt đầu* xa một từ mã, tôi không nghĩ bạn quan tâm nếu từ mã bị chuyển đổi, hoặc bạn kết thúc xa một từ mã (thực tế sẽ được phát hiện vì người xác minh đọc toàn bộ từ ở lớp cuối cùng)

@GuilleAngeris Nhân tiện, giả định trong bài báo này là chúng ta đang ở UDR phải không?

@UHaboeck @GiacomoFenzi Động lực của tôi chỉ là sửa lại tài liệu với "khoảng cách chỉnh sửa" nhỏ nhất. Cụ thể, tôi muốn giữ lại các sự kiện xấu chỉ là gập lại không làm giảm khoảng cách, thay vì sự kiện xấu hơi phức tạp hơn trong MCA.

@UHaboeck @GiacomoFenzi Sửa lại vì nó đang sử dụng phân tích sai từ tài liệu về khoảng cách gần này.

@UHaboeck @GiacomoFenzi Nghĩa là một trong những nhận định của tôi vào sáng nay là đối với truy vấn độc lập FRI, bạn có thể phân tích chỉ với CA "thông thường" thay vì có trọng số hoặc tương hỗ. Nhưng tôi đã làm điều này quá nhanh đến nỗi có thể ngày mai tôi sẽ phải ăn humble pie :)

@UHaboeck @GiacomoFenzi Và trên hết.. bạn cần chọn một lớp ngẫu nhiên để kiểm tra mỗi lần để có được giới hạn lỗi tốt nhất, thay vì truy vấn ở tất cả các lớp. Điều này liên quan đến (1-delta/t)^t lớn hơn 1-delta cho (ít nhất một số giá trị của) t>1

@aszepieniec *chúng ta đều có một lỗi chính tả - nó là (1-1/r)^r chứ không phải (1-r)^r

@aszepieniec *Cái `this` đầu tiên đề cập đến tweet ở trên, và cái `this` thứ hai đề cập đến tweet được liên kết :)

@aszepieniec Chính xác hơn, có vẻ như với khoảng cách delta đã cho, chúng ta có thể giới hạn xác suất thành công của truy vấn độc lập FRI bằng e^{-delta}, trong khi đối với FRI thông thường, chúng ta có thể đạt được 1-delta, ví dụ như nhỏ hơn khoảng ~0.1 khi delta=1/2