Το σχέδιο διόρθωσης σφαλμάτων «Μαγικό» αποδείχθηκε εγγενώς αναποτελεσματικό | Περιοδικό Quanta

Εάν έχετε στείλει ποτέ ένα μήνυμα κειμένου, παίξατε ένα CD ή αποθηκεύσατε ένα αρχείο στο cloud, έχετε επωφεληθεί από τη διόρθωση σφαλμάτων. Αυτή η επαναστατική ιδέα χρονολογείται από τη δεκαετία του 1940, όταν οι ερευνητές συνειδητοποίησαν για πρώτη φορά ότι είναι δυνατό να ξαναγράψουν οποιοδήποτε μήνυμα σε μια μορφή που επιτρέπει την εύκολη αντιστροφή της μεταγενέστερης διαφθοράς.

Με τα χρόνια, οι ερευνητές έχουν αναπτύξει πολλά έξυπνα σχήματα, που ονομάζονται κώδικες διόρθωσης σφαλμάτων, που κωδικοποιούν δεδομένα με διαφορετικούς τρόπους και χρησιμοποιούν διαφορετικές διαδικασίες για τη διόρθωση σφαλμάτων. Αλλά για τους θεωρητικούς επιστήμονες υπολογιστών, λίγοι είναι τόσο επιτακτικοί όσο οι λεγόμενοι τοπικά διορθωμένοι κώδικες. Αυτοί οι κωδικοί έχουν δύο ταυτόχρονες ιδιότητες που ακούγονται σχεδόν αντιφατικές: Οποιοδήποτε σφάλμα μπορεί να διορθωθεί διαβάζοντας τα κωδικοποιημένα δεδομένα σε λίγα μόνο σημεία, ωστόσο κανένας εισβολέας δεν μπορεί να ακυρώσει αυτή τη διαδικασία διόρθωσης παραβιάζοντας επιλεκτικά τον κώδικα. Είναι σαν να μπορούσατε να ανακτήσετε οποιαδήποτε σελίδα έχει κοπεί από ένα βιβλίο ρίχνοντας μια ματιά σε μερικές άλλες.

«Είναι ένα πολύ μαγικό φαινόμενο», είπε Τομ Γκουρ, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Κέιμπριτζ. "A priori, δεν είναι προφανές ότι ένα τέτοιο μαθηματικό αντικείμενο θα μπορούσε να υπάρχει καθόλου."

Αλλά αυτή η μαγεία έχει ένα μεγάλο κόστος. Τα μόνα γνωστά παραδείγματα τοπικά διορθώσιμων κωδικών είναι εξαιρετικά αναποτελεσματικά — η κωδικοποίηση οποιουδήποτε μηνύματος το κάνει επίσης εκθετικά μεγαλύτερο. Ολόκληρα βιβλία που κωδικοποιούνται με αυτόν τον τρόπο θα ήταν υπερβολικά δυσκίνητα.

Οι επιστήμονες υπολογιστών έχουν από καιρό αναρωτηθεί εάν είναι δυνατοί καλύτεροι τοπικά διορθωμένοι κωδικοί. Έχουν επικεντρωθεί ειδικά σε κώδικες που χρησιμοποιούν μόνο τρία ερωτήματα για τη διόρθωση οποιουδήποτε σφάλματος, ελπίζοντας ότι αυτός ο αυστηρός περιορισμός μπορεί να κάνει αυτούς τους κωδικούς πιο κατανοητούς. Αλλά ακόμη και αυτή η απλή υπόθεση έχει παραπλανήσει τους ερευνητές για πάνω από 20 χρόνια.

Τώρα ο επιστήμονας υπολογιστών Pravesh Kothari του Πανεπιστημίου Carnegie Mellon και ο μεταπτυχιακός φοιτητής του Πήτερ Μανοχάρ επιτέλους αποδείχθηκε ότι είναι αδύνατο να δημιουργηθεί ένας τοπικά διορθώσιμος κώδικας τριών ερωτημάτων που να αποφεύγει αυτό το εκθετικό κόστος. Μπορεί να είναι ένα αρνητικό αποτέλεσμα, αλλά οτιδήποτε διευκρινίζει τα όρια της διόρθωσης σφαλμάτων είναι συναρπαστικό για τους ερευνητές, ειδικά επειδή τα μαθηματικά των τοπικά διορθώσιμων κωδικών εμφανίζονται σε περιοχές μακριά από την επικοινωνία.

«Αυτό το αποτέλεσμα είναι εκπληκτικό», είπε Σουμπανγκί Σαράφ, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Τορόντο. «Είναι μια τεράστια ανακάλυψη».

Δύναμη στους αριθμούς

Για να κατανοήσετε τη διόρθωση σφαλμάτων, φανταστείτε τα δεδομένα που θέλετε να προστατεύσετε ως μια ακολουθία bit ή 0 και 1. Ένα σφάλμα, σε αυτό το μοντέλο, μπορεί να είναι οποιαδήποτε ανεπιθύμητη ανατροπή του 0 σε 1 ή αντίστροφα, είτε οφείλεται σε τυχαία διακύμανση είτε σε σκόπιμη παραβίαση.

Ας υποθέσουμε ότι θέλετε να στείλετε ένα μήνυμα σε έναν φίλο, αλλά ανησυχείτε ότι τα σφάλματα ενδέχεται να αλλάξουν το νόημα. Μια απλή στρατηγική είναι να αντικαταστήσετε κάθε 0 στο μήνυμά σας με 000 και κάθε 1 με 111. Εάν ο φίλος σας δει ένα μέρος του μηνύματος που δεν περιέχει τρία ίδια bit στη σειρά, θα καταλάβει ότι έχει προκύψει σφάλμα. Και αν τα σφάλματα είναι τυχαία και σχετικά σπάνια, τότε οποιαδήποτε συμβολοσειρά του 110 είναι πολύ πιο πιθανό να είναι ένα κατεστραμμένο 111 από ένα κατεστραμμένο 000. Μια απλή ψήφος πλειοψηφίας σε κάθε τριάδα θα αρκεί για να διορθωθούν τα περισσότερα λάθη.

Αυτό το σχήμα, που ονομάζεται κώδικας επανάληψης, έχει την αρετή της απλότητας, αλλά δεν μπορεί να το προτείνει. Πρώτον, απαιτεί τριπλασιασμό του μήκους κάθε μηνύματος μόνο για την αντιμετώπιση σχετικά σπάνιων σφαλμάτων, και εάν υπάρχει μια αξιοπρεπής πιθανότητα δύο παρακείμενων σφαλμάτων, θα χρειαστούμε ακόμη περισσότερο πλεονασμό. Ακόμη χειρότερα, γίνεται γρήγορα άχρηστο εάν τα σφάλματα δεν είναι τυχαία, όπως όταν οι εισβολείς προσπαθούν ενεργά να υπονομεύσουν τον κώδικα. Στον κώδικα επανάληψης, όλες οι πληροφορίες που απαιτούνται για τη διόρθωση ενός δεδομένου bit αποθηκεύονται σε λίγα μόνο άλλα bit, αφήνοντάς το ευάλωτο σε μια στοχευμένη επίθεση.

Ευτυχώς, πολλοί κωδικοί διόρθωσης σφαλμάτων έχουν καλύτερη απόδοση. Ένα διάσημο παράδειγμα, που ονομάζεται το Κώδικας Reed-Solomon, λειτουργεί μετατρέποντας μηνύματα σε πολυώνυμα — μαθηματικές εκφράσεις όπως x² + 3x + 2 που αποτελούνται από διαφορετικούς όρους που προστίθενται μαζί, ο καθένας με μια μεταβλητή (π.χ x) ανυψώθηκε σε διαφορετική δύναμη. Η κωδικοποίηση ενός μηνύματος χρησιμοποιώντας έναν κώδικα Reed-Solomon περιλαμβάνει τη δημιουργία ενός πολυωνύμου με έναν όρο για κάθε χαρακτήρα του μηνύματος, στη συνέχεια σχεδιάζοντας το πολυώνυμο ως καμπύλη σε ένα γράφημα και αποθηκεύοντας τις συντεταγμένες των σημείων που βρίσκονται στην καμπύλη (λαμβάνοντας τουλάχιστον ένα ακόμη σημείο από τον αριθμό των χαρακτήρων). Τα σφάλματα μπορεί να απομακρύνουν μερικά από αυτά τα σημεία από την καμπύλη, αλλά αν δεν υπάρχουν πάρα πολλά σφάλματα, μόνο μία πολυωνυμική καμπύλη θα περάσει από τα περισσότερα σημεία. Αυτή η καμπύλη αντιστοιχεί σχεδόν σίγουρα στο αληθινό μήνυμα.

Οι κώδικες Reed-Solomon είναι υπεραποτελεσματικοί — χρειάζεται μόνο να αποθηκεύσετε μερικούς επιπλέον πόντους για να διορθώσετε τα σφάλματα, επομένως οποιοδήποτε κωδικοποιημένο μήνυμα είναι οριακά μόνο μεγαλύτερο από το αρχικό. Είναι επίσης λιγότερο ευάλωτα στο είδος της στοχευμένης διακοπής που θα σήμαινε καταστροφή για τον κωδικό επανάληψης, επειδή οι πληροφορίες που χρησιμοποιούνται για τη διόρθωση ενός σφάλματος οπουδήποτε διανέμονται σε ολόκληρο το κωδικοποιημένο μήνυμα.

Σκεφτείτε Παγκόσμια, Δράστε Τοπικά

Η δύναμη του κώδικα Reed-Solomon πηγάζει από τη διασύνδεση. Αλλά ακριβώς λόγω αυτής της διασύνδεσης, δεν υπάρχει τρόπος να διορθώσετε ένα μόνο σφάλμα σε ένα κωδικοποιημένο μήνυμα χωρίς να διαβάσετε ολόκληρο το θέμα. Αυτό μπορεί να μην ακούγεται ως πρόβλημα στο πλαίσιο της επικοινωνίας: Εάν στέλνετε ένα μήνυμα, πιθανότατα θέλετε ο παραλήπτης να το διαβάσει όλο. Αλλά μπορεί να είναι μια υποχρέωση στην αποθήκευση δεδομένων - μια άλλη σημαντική εφαρμογή διόρθωσης σφαλμάτων.

Σκεφτείτε μια εταιρεία που αποθηκεύει τα email των χρηστών στο cloud — δηλαδή σε μια τεράστια γκάμα διακομιστών. Μπορείτε να σκεφτείτε ολόκληρη τη συλλογή των email ως ένα μεγάλο μήνυμα. Τώρα ας υποθέσουμε ότι ένας διακομιστής κολλάει. Με έναν κώδικα Reed-Solomon, θα χρειαστεί να εκτελέσετε έναν τεράστιο υπολογισμό που περιλαμβάνει όλα τα κωδικοποιημένα δεδομένα για να ανακτήσετε τα email σας από αυτόν τον έναν χαμένο διακομιστή. «Θα έπρεπε να κοιτάξεις τα πάντα», είπε Zeev Dvir, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Πρίνστον. «Αυτά θα μπορούσαν να είναι δισεκατομμύρια και δισεκατομμύρια email — θα μπορούσε να πάρει πολύ χρόνο».

Οι ερευνητές χρησιμοποιούν τον όρο "τοπικό" για να περιγράψουν κώδικες που χρησιμοποιούν μόνο ένα κλάσμα του κωδικοποιημένου μηνύματος σημειακά λάθη ή διορθώστε τα. Ο απλός κώδικας επανάληψης έχει κάτι από αυτόν τον τοπικό χαρακτήρα, αλλά αυτό ακριβώς τον κάνει τόσο ευάλωτο σε παραβίαση. Ένας τοπικά διορθώσιμος κώδικας, αντίθετα, λαμβάνει το καλύτερο και των δύο κόσμων — μπορεί να διορθώσει ένα σφάλμα σε οποιοδήποτε κομμάτι με λίγα μόνο ερωτήματα, όλα αυτά χωρίς να χάσει τη διασύνδεση που κάνει τους κώδικες Reed-Solomon τόσο ανθεκτικούς.

«Αυτή είναι μια πραγματικά αυστηρή ιδέα», είπε ο Kothari.

Τα πιο διάσημα παραδείγματα τοπικά διορθώσιμων κωδικών είναι εκδόσεις ενός αξιοσέβαστου κώδικα διόρθωσης σφαλμάτων που εφευρέθηκε το 1954 από τους μαθηματικούς Ντέιβιντ Μύλλερ και Ίρβινγκ Ριντ (ο οποίος βοήθησε επίσης στην ανάπτυξη των κωδίκων Reed-Solomon). Όπως οι κώδικες Reed-Solomon, οι κώδικες Reed-Muller χρησιμοποιούν πολυώνυμα με πολλούς όρους που προστίθενται μαζί για να κωδικοποιήσουν μεγάλα μηνύματα.

Τα πολυώνυμα που χρησιμοποιούνται στους κώδικες Reed-Solomon περιλαμβάνουν μία μόνο μεταβλητή, x, επομένως ο μόνος τρόπος για να προσθέσετε περισσότερους όρους είναι να χρησιμοποιήσετε υψηλότερες δυνάμεις του x. Αυτό έχει ως αποτέλεσμα μια καμπύλη με πολλές κινήσεις που μπορεί να καρφωθεί μόνο κοιτάζοντας πολλά σημεία. Οι κώδικες Reed-Muller χρησιμοποιούν αντ' αυτού πολυώνυμα στα οποία κάθε όρος μπορεί να περιέχει πολλαπλές μεταβλητές πολλαπλασιασμένες μαζί. Περισσότερες μεταβλητές σημαίνουν περισσότερους τρόπους συνδυασμού τους, κάτι που με τη σειρά του προσφέρει έναν τρόπο αύξησης του αριθμού των πολυωνυμικών όρων χωρίς να αυξήσει καμία μεμονωμένη μεταβλητή σε τόσο υψηλές δυνάμεις.

Οι κωδικοί Reed-Muller είναι πολύ ευέλικτοι. Μπορείτε να κωδικοποιήσετε μεγαλύτερα μηνύματα αυξάνοντας την υψηλότερη ισχύ που εμφανίζεται στο πολυώνυμο, αυξάνοντας τον αριθμό των μεταβλητών ή και τα δύο. Για να διορθώσετε έναν κώδικα Reed-Muller τοπικά, απλώς περιορίζετε τη μέγιστη ισχύ κάθε μεταβλητής σε μια μικρή σταθερή τιμή και χειρίζεστε μεγαλύτερα μηνύματα αυξάνοντας μόνο τον αριθμό των μεταβλητών.

Ειδικά για έναν τοπικά διορθώσιμο κώδικα τριών ερωτημάτων, αυτή η μέγιστη ισχύς ορίζεται στο 2. Στη συνέχεια, όσον αφορά κάθε μεμονωμένη μεταβλητή, το πολυώνυμο που κωδικοποιεί το μήνυμα ανιχνεύει μια απλή παραβολή. Για να προσδιορίσετε το ακριβές σχήμα αυτής της παραβολής, χρειάζεται μόνο να εξετάσετε την καμπύλη σε τρία σημεία. Επιπλέον, με πολλές μεταβλητές υπάρχουν πολλές τέτοιες παραβολές, οποιαδήποτε από τις οποίες μπορεί να χρησιμοποιηθεί για τη διόρθωση σφαλμάτων. Αυτό είναι που κάνει τους κώδικες Reed-Muller τόσο ανθεκτικούς.

Δυστυχώς, ο κώδικας Reed-Muller έχει ένα σοβαρό μειονέκτημα: Ο αριθμός των bit που απαιτούνται για την κωδικοποίηση ενός μηνύματος αυξάνεται εκθετικά με τον αριθμό των μεταβλητών. Εάν θέλετε έναν εξαιρετικά τοπικό κώδικα που διορθώνει τα σφάλματα με λίγα μόνο ερωτήματα, θα χρειαστείτε πολλές μεταβλητές για μεγάλα μηνύματα και ο κώδικας Reed-Muller θα γίνει γρήγορα άχρηστος στην πράξη.

«Το εκθετικό σε αυτή την περίπτωση είναι πολύ κακό», είπε ο Dvir. Είναι όμως αναπόφευκτο;

Διορθώσιμο ή αποκωδικοποιήσιμο;

Καθώς οι επιστήμονες υπολογιστών προσπάθησαν και απέτυχαν να βρουν πιο αποτελεσματικούς τοπικά διορθώσιμους κωδικούς, άρχισαν να υποψιάζονται ότι τέτοιοι κωδικοί δεν ήταν καθόλου δυνατοί. Το 2003, δύο ερευνητές αποδείχθηκε ότι δεν υπάρχει τρόπος να νικήσετε τον κώδικα Reed-Muller χρησιμοποιώντας μόνο δύο ερωτήματα. Αλλά αυτό είναι τόσο μακριά όσο κανείς.

«Μόλις πάτε στα τρία, οι γνώσεις μας γίνονται πολύ πρόχειρες», είπε ο Kothari.

Η επόμενη ανακάλυψη απλώς περιέπλεξε περαιτέρω τα πράγματα. Σε δύο άρθρα που δημοσιεύτηκαν στο 2008 και 2009, οι επιστήμονες υπολογιστών Sergey Yekhanin και Klim Efremenko έδειξαν πώς να κατασκευαστούν κώδικες τριών ερωτημάτων που ήταν πιο αποτελεσματικοί από τους κώδικες Reed-Muller, αλλά αυτοί οι κώδικες δεν ήταν τοπικά διορθωμένοι. Αντίθετα, είχαν μια διακριτικά διαφορετική ιδιότητα που ονομάζεται τοπική αποκωδικοποίηση.

Για να κατανοήσουμε τη διαφορά, ας φανταστούμε ξανά έναν πάροχο αποθήκευσης cloud που συνδυάζει τα δεδομένα των χρηστών σε ένα μεγάλο μήνυμα και το προστατεύει χρησιμοποιώντας έναν κωδικό διόρθωσης σφαλμάτων. Τόσο οι τοπικά διορθώσιμοι κωδικοί όσο και οι τοπικά αποκωδικοποιήσιμοι κωδικοί μπορούν να διορθώσουν ένα σφάλμα σε οποιοδήποτε κομμάτι του αρχικού μηνύματος με λίγα μόνο ερωτήματα.

Αλλά κάθε κώδικας διόρθωσης σφάλματος απαιτεί επίσης επιπλέον bits που δεν υπήρχαν στο αρχικό μήνυμα - γι' αυτό η κωδικοποίηση ενός μηνύματος το κάνει μεγαλύτερο. Οι δύο τύποι κωδικών διαφέρουν ως προς τον τρόπο με τον οποίο χειρίζονται αυτά τα πρόσθετα bits. Οι τοπικά αποκωδικοποιήσιμοι κωδικοί δεν υπόσχονται τον αριθμό των ερωτημάτων που απαιτούνται για τη διόρθωση σφαλμάτων σε αυτά τα bit. Αλλά σε έναν τοπικά διορθώσιμο κώδικα, ένα σφάλμα σε οποιοδήποτε από τα επιπλέον bit μπορεί να διορθωθεί με τον ίδιο ακριβώς τρόπο όπως ένα σφάλμα σε οποιοδήποτε bit του αρχικού μηνύματος.

"Ό,τι αποθηκεύετε, είτε πρόκειται για τα αρχικά δεδομένα των χρηστών είτε για τον πλεονασμό και τις πληροφορίες ελέγχου — όλα αυτά μπορούν να διορθωθούν τοπικά", είπε. Madhu Sudan, επιστήμονας υπολογιστών στο Πανεπιστήμιο του Χάρβαρντ.

Αν και διαφέρουν κατ' αρχήν, η τοπική διόρθωση και η τοπική αποκωδικοποίηση έμοιαζαν πάντα εναλλάξιμα στην πράξη πριν από το 2008 — κάθε γνωστός τοπικά αποκωδικοποιήσιμος κώδικας ήταν επίσης τοπικά διορθωτός. Η ανακάλυψη του Yekhanin και του Efremenko έθεσε την πιθανότητα μιας θεμελιώδης διαφοράς μεταξύ των δύο συνθηκών. Ή ίσως ήταν δυνατό να τροποποιηθούν οι κώδικες του Yekhanin και του Efremenko για να γίνουν τοπικά διορθώσιμοι. Αυτό θα έθεσε τις δύο προϋποθέσεις σε ίση βάση για άλλη μια φορά, αλλά θα σήμαινε επίσης ότι οι ερευνητές είχαν κάνει λάθος σχετικά με το πόσο αποτελεσματικοί θα μπορούσαν να λάβουν οι τοπικά διορθώσιμοι κώδικες τριών ερωτημάτων. Είτε έτσι είτε αλλιώς, η συμβατική σοφία θα έπρεπε να αλλάξει.

Λογική Δανεισμού

Οι Kothari και Manohar έλυσαν τελικά αυτή την ένταση προσαρμόζοντας μια τεχνική από μια διαφορετική περιοχή της επιστήμης των υπολογιστών: τη μελέτη των λεγόμενων προβλημάτων ικανοποίησης περιορισμών. Το να προσπαθείς να συντονίσεις τα σχέδια για δείπνο με μια ομάδα φίλων είναι ένα πρόβλημα ικανοποίησης περιορισμών. Ο καθένας έχει επιλογές που θα αποδεχθεί και επιλογές που θα ασκήσει βέτο. Η δουλειά σας είναι είτε να βρείτε ένα σχέδιο που να ικανοποιεί όλους ή, αν δεν υπάρχει τέτοιο σχέδιο, να το καταλάβετε το συντομότερο δυνατό.

Υπάρχει μια εγγενής ασυμμετρία μεταξύ αυτών των δύο πιθανών αποτελεσμάτων. Μια αποδεκτή λύση μπορεί να μην είναι εύκολο να βρεθεί, αλλά μόλις την αποκτήσετε, είναι εύκολο να πείσετε οποιονδήποτε άλλον ότι θα λειτουργήσει. Αλλά ακόμα κι αν γνωρίζετε ότι το πρόβλημα είναι πραγματικά «μη ικανοποιητικό», μπορεί να μην υπάρχει ένα παράδειγμα που να παρέχει απόδειξη.

Το 2021, ο Kothari και ο Manohar, μαζί με τον Venkatesan Guruswami του Πανεπιστημίου της Καλιφόρνια, στο Μπέρκλεϋ, έκαναν μια σημαντική ανακάλυψη στη μελέτη των προβλημάτων ικανοποίησης περιορισμών χρησιμοποιώντας μια νέα θεωρητική τεχνική για τον εντοπισμό αυτών των δύσκολων μη ικανοποιητικών περιπτώσεων. Υποψιάζονταν ότι η νέα μέθοδος θα ήταν ένα ισχυρό εργαλείο για την επίλυση και άλλων προβλημάτων και ο μεταπτυχιακός φοιτητής του Guruswami, Omar Alrabiah, πρότεινε να εξετάσουν τοπικά αποκωδικοποιήσιμους κώδικες τριών ερωτημάτων.

«Αυτό ήταν ένα καρφί με ένα σφυρί στο χέρι μας, να το πω έτσι», είπε ο Kothari.

Τα εκπληκτικά αποτελέσματα των Yekhanin και Efremenko είχαν δείξει ότι οι τοπικά αποκωδικοποιήσιμοι κώδικες τριών ερωτημάτων θα μπορούσαν να είναι πιο αποτελεσματικοί από τους κώδικες Reed-Muller. Ήταν όμως οι καλύτεροι δυνατοί κωδικοί τους ή θα μπορούσαν οι τοπικά αποκωδικοποιήσιμοι κώδικες τριών ερωτημάτων να γίνουν ακόμη πιο αποτελεσματικοί; Οι Kothari, Manohar, Guruswami και Alrabiah σκέφτηκαν ότι η νέα τους τεχνική θα μπορούσε να αποδείξει όρια στο πόσο αποτελεσματικοί θα μπορούσαν να γίνουν τέτοιοι κώδικες. Το σχέδιό τους ήταν να οικοδομήσουν μια λογική φόρμουλα που θα περιλάμβανε τη δομή όλων των πιθανών τοπικά αποκωδικοποιήσιμων κωδικών τριών ερωτημάτων ενός δεδομένου μεγέθους, και να αποδείξουν ότι δεν ήταν ικανοποιητικός, δείχνοντας έτσι ότι δεν θα μπορούσε να υπάρξει τέτοιος κώδικας.

Οι τέσσερις ερευνητές έκαναν ένα πρώτο βήμα προς αυτή την κατεύθυνση το 2022, θέτοντας α νέο όριο σχετικά με τη μέγιστη απόδοση των κωδικών τοπικά αποκωδικοποιήσιμων τριών ερωτήσεων. Το αποτέλεσμα ξεπέρασε πολύ αυτό που οι ερευνητές είχαν καταφέρει να επιτύχουν με άλλες τεχνικές, αλλά δεν απέκλεισε όλους τους κωδικούς πιο αποτελεσματικούς από εκείνους του Yekhanin και του Efremenko.

Ο Kothari και ο Manohar υποψιάστηκαν ότι θα μπορούσαν να προχωρήσουν παραπέρα. Αλλά η πρόοδος σταμάτησε μέχρι που ο Manohar σημείωσε έναν γρήγορο υπολογισμό στο πίσω μέρος του φακέλου, υποδεικνύοντας ότι η τεχνική μπορεί να λειτουργήσει ακόμη καλύτερα για τοπικά διορθώσιμους κωδικούς από ό,τι για τοπικά αποκωδικοποιήσιμους κωδικούς.

Λίγους μήνες αργότερα, μετά από πολλές ακόμα λανθασμένες εκκινήσεις που τους έκαναν να φοβούνται ότι ήταν πολύ αισιόδοξοι, η τεχνική επιτέλους πέτυχε την υπόσχεσή της. Οι Kothari και Manohar απέδειξαν ότι, όπως υποψιάστηκαν οι ερευνητές, είναι αδύνατο για τοπικά διορθώσιμο κώδικα τριών ερωτημάτων να λειτουργήσει πολύ καλύτερα από τους κώδικες Reed-Muller. Αυτή η εκθετική κλιμάκωση είναι ένας θεμελιώδης περιορισμός. Το αποτέλεσμά τους ήταν επίσης μια δραματική απόδειξη ότι η τοπική διόρθωση και η τοπική αποκωδικοποίηση, αν και επιφανειακά παρόμοια, διαφέρουν πραγματικά σε ένα θεμελιώδες επίπεδο: Το τελευταίο είναι αναμφισβήτητα πιο εύκολο να γίνει αντιληπτό από το πρώτο.

Οι Kothari και Manohar ελπίζουν τώρα να επεκτείνουν τις τεχνικές τους για να μελετήσουν κώδικες που επιτρέπεται να κάνουν περισσότερα από τρία ερωτήματα, καθώς πολύ λίγα είναι γνωστά για αυτούς τώρα. Και η πρόοδος στη θεωρία της διόρθωσης σφαλμάτων έχει συχνά επιπτώσεις σε άλλα φαινομενικά άσχετα πεδία. Συγκεκριμένα, οι τοπικά διορθωμένοι κωδικοί κάνουν εμφανίσεις έκπληξη παντού από το πρόβλημα του ιδιωτικές αναζητήσεις βάσεων δεδομένων στην κρυπτογραφία σε αποδείξεις του θεωρήματα στη συνδυαστική. Είναι πολύ νωρίς για να πούμε πώς η τεχνική των Kothari και Manohar θα επηρεάσει αυτά τα διαφορετικά πεδία, αλλά οι ερευνητές αισθάνονται αισιόδοξοι.

«Υπάρχει μια πολύ όμορφη νέα ιδέα εδώ», είπε ο Dvir. «Πιστεύω ότι υπάρχουν πολλές δυνατότητες».