Sachverhalt:
A.
Der 1960 geborene A._ meldete sich am 15. Februar 2002 unter Hinweis auf Rückenbeschwerden sowie ein depressives Zustandsbild bei der IV-Stelle des Kantons Zürich zum Bezug einer IV-Rente an. Mit Verfügung vom 11. März 2003 sprach ihm die IV-Stelle bei einem Invaliditätsgrad von 100 % eine ganze IV-Rente zu. Infolge einer revisionsweisen Überprüfung des Rentenanspruchs setzte die IV-Stelle die ganze Rente am 9. Oktober 2008 auf eine Dreiviertelsrente herab.
Am 7. November 2013 teilten die behandelnden Psychiater der Psychiatrischen Klinik B._ der IV-Stelle mit, dass sich der Gesundheitszustand von A._ verschlechtert habe. Die IV-Stelle klärte die medizinische Situation ab und holte u.a. bei Dr. med. C._, Facharzt FMH für Psychiatrie und Psychotherapie, ein psychiatrisches Gutachten ein (Gutachten vom 13. Juni 2014). Nach Durchführung des Vorbescheidverfahrens hob die IV-Stelle die Rente mit Verfügung vom 11. Mai 2015 per Ende Juni 2015 auf.
B.
Das Sozialversicherungsgericht des Kantons Zürich hiess die dagegen erhobene Beschwerde mit Entscheid vom 3. Oktober 2016 in dem Sinn gut, als es A._ in Aufhebung der Verfügung vom 11. Mai 2015 ab 1. Juli 2015 eine Viertelsrente zusprach.
C.
Die IV-Stelle führt Beschwerde in öffentlich-rechtlichen Angelegenheiten mit dem Rechtsbegehren, in Aufhebung dieses Entscheids sei die Verfügung vom 11. Mai 2015 zu bestätigen sowie festzustellen, dass kein Rentenanspruch bestehe. Zudem sei der Beschwerde die aufschiebende Wirkung zuzuerkennen.
A._ beantragt in seiner Stellungnahme eine neue psychiatrische Begutachtung. Für den Fall, dass die Sache nicht zur medizinischen Neubeurteilung an die Vorinstanz zurückgewiesen werde, sei die Beschwerde abzuweisen. Ferner sei die aufschiebende Wirkung nicht zu gewähren. Die Vorinstanz und das Bundesamt für Sozialversicherungen verzichten auf eine Vernehmlassung.

Erwägungen:
1.
1.1. Die Beschwerde in öffentlich-rechtlichen Angelegenheiten kann wegen Rechtsverletzungen gemäss Art. 95 f. BGG erhoben werden. Das Bundesgericht wendet das Recht von Amtes wegen an (<ref-law>), doch prüft es, unter Berücksichtigung der allgemeinen Rüge- und Begründungspflicht (Art. 42 Abs. 1 und 2 BGG), nur die geltend gemachten Vorbringen, falls allfällige weitere rechtliche Mängel nicht geradezu offensichtlich sind (<ref-ruling> E. 1.6 S. 280 f.; <ref-ruling> E. 1.4.1 S. 254).
1.2. Das Bundesgericht legt seinem Urteil den Sachverhalt zugrunde, den die Vorinstanz festgestellt hat (<ref-law>). Es kann deren Sachverhaltsfeststellung nur berichtigen oder ergänzen, wenn sie offensichtlich unrichtig ist oder auf einer Rechtsverletzung im Sinne von <ref-law> beruht (<ref-law>). Überdies muss die Behebung des Mangels für den Ausgang des Verfahrens entscheidend sein (<ref-law>).
2.
2.1. Im Rahmen des Einkommensvergleichs (<ref-law>) ging die Vorinstanz sowohl beim Validen- als auch beim Invalideneinkommen vom Durchschnittslohn (Zentralwert) für Männer für einfache Tätigkeiten körperlicher oder handwerklicher Art (Kompetenzniveau 1 der vom Bundesamt für Statistik herausgegebenen Schweizerischen Lohnstrukturerhebung [LSE] 2012, Tabelle TA1, Privater Sektor Schweiz) aus. Während die IV-Stelle keinen leidensbedingten Abzug gewährt und einen Invaliditätsgrad von 30 % errechnet hatte, erachtete das kantonale Gericht einen Abzug vom Tabellenlohn von 15 % als angebracht, weil der Beschwerdegegner lediglich noch in einem Teilzeitpensum tätig sein könne und wegen langjährigem Rentenbezug seit langem vom Arbeitsmarkt abwesend gewesen sei. Daraus resultiere ein Invaliditätsgrad von rund 40 %, somit habe der Versicherte Anspruch auf eine Viertelsrente.
2.2. Die Beschwerde der IV-Stelle richtet sich einzig gegen den Abzug vom Tabellenlohn. Demgegenüber wirft der Beschwerdegegner der Vorinstanz vor, sie habe durch das Abstellen auf das Gutachten des Dr. med. C._ den Sachverhalt offensichtlich unrichtig festgestellt und eine willkürliche Beweiswürdigung vorgenommen. Ebenso habe sie ein zu tiefes Valideneinkommen angenommen. Daher beantragt er die Rückweisung zur erneuten Begutachtung unter gleichzeitiger Ausrichtung mindestens einer Viertelsrente. Andernfalls sei die Beschwerde abzuweisen.
2.3.
2.3.1. Im Verfahren vor Bundesgericht gibt es keine Anschlussbeschwerde (<ref-ruling> E. 2.1 S. 110; <ref-ruling> E. 2.5 S. 335). Wer mit dem angefochtenen Entscheid nicht einverstanden ist, muss diesen selbst innert der Beschwerdefrist (<ref-law>) anfechten. Sodann kann das Bundesgericht nicht über die fristgerecht gestellten Rechtsbegehren der Parteien hinausgehen (<ref-law>), wobei Ausgangspunkt der Bindungswirkung das Rechtsbegehren der beschwerdeführenden Partei, nicht jenes des Beschwerdegegners ist (MEYER/DORMANN, in: Basler Kommentar zum BGG, 2. Aufl. 2011, N. 2 zu <ref-law>). Gibt die Vorinstanz - wie hier - beiden Parteien teilweise Recht und erhebt nur eine Partei Beschwerde ans Bundesgericht mit dem Antrag, es sei ihr vollumfänglich Recht zu geben, kann deshalb die andere Partei nicht im Rahmen der Vernehmlassung zu dieser Beschwerde wieder diejenigen Anträge stellen, bezüglich welcher die Vorinstanz ihr Unrecht gegeben hat (zum Ganzen: <ref-ruling> E. 2.1 S. 110; Urteil 8C_446/2014 vom 12. Januar 2015 E. 2.1).
2.3.2. Der Beschwerdegegner hat darauf verzichtet, den kantonalen Entscheid innert der Beschwerdefrist anzufechten. Soweit er sich nun in der Vernehmlassung auf eine offensichtlich unrichtige Sachverhaltsfeststellung beruft, die Rückweisung der Sache zur Neubegutachtung beantragt und geltend macht, dies könne zu einer höheren Rente führen, als sie die Vorinstanz festgesetzt habe, hätte er seine Einwände allerdings mit eigener Beschwerde in das Verfahren einbringen müssen. Deshalb ist auf seine Vorbringen nicht einzutreten, soweit sie über den Antrag auf Beschwerdeabweisung hinausgehen.
3.
Streitig und zu prüfen bleibt, ob dem Versicherten ein Abzug vom Tabellenlohn zu gewähren ist.
3.1. Wird das Invalideneinkommen auf der Grundlage von statistischen Durchschnittswerten ermittelt, ist der entsprechende Ausgangswert (Tabellenlohn) allenfalls zu kürzen. Damit soll der Tatsache Rechnung getragen werden, dass persönliche und berufliche Merkmale, wie Art und Ausmass der Behinderung, Lebensalter, Dienstjahre, Nationalität oder Aufenthaltskategorie und Beschäftigungsgrad Auswirkungen auf die Lohnhöhe haben können (<ref-ruling> E. 3b/aa S. 323). Aufgrund dieser Faktoren kann die versicherte Person die verbliebene Arbeitsfähigkeit auch auf einem ausgeglichenen Arbeitsmarkt möglicherweise nur mit unterdurchschnittlichem erwerblichem Erfolg verwerten (<ref-ruling> E. 5b/aa in fine S. 80). Der Abzug soll aber nicht automatisch erfolgen. Er ist unter Würdigung der Umstände im Einzelfall nach pflichtgemässem Ermessen gesamthaft zu schätzen und darf 25 % nicht übersteigen (<ref-ruling> E. 5.2 S. 301; <ref-ruling> E. 5.2 S. 327 f.; <ref-ruling> E. 5b/bb-cc S. 80). Die Rechtsprechung gewährt insbesondere dann einen Abzug auf dem Invalideneinkommen, wenn eine versicherte Person selbst im Rahmen körperlich leichter Hilfsarbeitertätigkeit in ihrer Leistungsfähigkeit eingeschränkt ist (<ref-ruling> E. 5a/bb S. 78). Zu beachten ist jedoch, dass allfällige bereits in der Beurteilung der medizinischen Arbeitsfähigkeit enthaltene gesundheitliche Einschränkungen nicht zusätzlich in die Bemessung des leidensbedingten Abzugs einfliessen und so zu einer doppelten Anrechnung desselben Gesichtspunkts führen dürfen (Urteil 9C_846/2014 vom 22. Januar 2015 E. 4.1.1 mit Hinweisen).
Ob ein (behinderungsbedingt oder anderweitig begründeter) Abzug vom Tabellenlohn vorzunehmen ist, stellt eine vom Bundesgericht frei überprüfbare Rechtsfrage dar (Urteil 8C_652/2008 vom 8. Mai 2009 E. 4, nicht publ. in: <ref-ruling>). Dagegen ist die Höhe des (im konkreten Fall grundsätzlich angezeigten) Abzugs eine Ermessensfrage und daher letztinstanzlich nur bei Ermessensüberschreitung, -missbrauch oder -unterschreitung korrigierbar (<ref-ruling> E. 5.1 S. 72 f.; <ref-ruling> E. 3.3 S. 399; Urteil 8C_477/2016 vom 23. November 2016 E. 4.1).
3.2. Grundsätzlich ist ein Abzug vom Tabellenlohn vorzunehmen, wenn ein Versicherter seine Arbeitsfähigkeit nicht vollschichtig umsetzen kann, weil Teilzeitarbeit bei Männern statistisch gesehen vergleichsweise weniger gut entlöhnt wird als eine Vollzeittätigkeit (vgl. Urteile 8C_482/2016 vom 15. September 2016 E. 5.4.3; 9C_721/2010 vom 15. November 2010 E. 4.2.2, in: SVR 2011 IV Nr. 37 S. 109). Allerdings muss dies stets mit Blick auf den konkreten Beschäftigungsgrad (vorliegend 70 %) und die jeweils aktuellen Werte beurteilt werden: Laut der gestützt auf die LSE 2012 erstellten Tabelle zu den nach Beschäftigungsgrad, Geschlecht und beruflicher Stellung differenzierten monatlichen Durchschnittsbruttolöhnen rechtfertigt ein Beschäftigungsgrad von 70 % bei Männern auf der untersten Stufe der beruflichen Stellung (ohne Kaderfunktion) keinen zusätzlichen Tabellenlohnabzug (Bundesamt für Sozialversicherungen, IV-Rundschreiben Nr. 328 vom 22. Oktober 2014, Anhang; vgl. dazu <ref-ruling> E. 2.5.1 S. 184 mit Hinweis), wie die Beschwerdeführerin zu Recht geltend macht. Denn auf dieser Ebene besteht bei Männern zwischen dem Durchschnittslohn bei einem Teilzeitpensum von 50-74 % proportional bezogen auf ein 100 %-Pensum (Fr. 6'080.-) und dem Durchschnittslohn bei einem Vollzeitpensum (Fr. 6'085.-) kein wesentlicher Unterschied (Urteile 8C_549/2016 vom 19. Januar 2017 E. 6; 8C_516/2014 vom 6. Januar 2015 E. 10.2; vgl. Urteil 8C_622/2016 vom 21. Dezember 2016 E. 5.3.2). In der für das Jahr 2014 aktualisierten Tabelle beläuft sich die Differenz bei den angegebenen Werten (Fr. 5'714.- [Teilzeitpensum] und Fr. 6'069.- [Vollzeitpensum]) zwar auf Fr. 355.- (oder 5,85 %). Allerdings ergibt sich daraus einerseits keine überproportionale Lohneinbusse, so dass sich die Verweigerung eines (zusätzlichen) Abzugs auch angesichts dieser neueren Zahlen jedenfalls nicht als bundesrechtswidrig erweist (vgl. Urteil 8C_12/2017 vom 28. Februar 2017 E. 5.5.2 mit Hinweis). Andererseits würden die neuen Werte bestenfalls einen (zusätzlichen) Abzug im Umfang von 5 bis 6 % erlauben. Ob diese neuen Zahlen allenfalls anzuwenden wären und ob deswegen ein Abzug zu gewähren wäre, muss jedoch nicht näher geprüft werden, weil ein Abzug in dieser Höhe im hier zu beurteilenden Fall nicht zu einem Rentenanspruch führen würde, wie die folgenden Erwägungen zeigen (s. E. 3.3 und 3.4). Etwas anderes ergibt sich schliesslich auch nicht aus dem Urteil 9C_808/2015 vom 29. Februar 2016, auf das der Beschwerdegegner hinweist, denn dort wird auf Zahlen aus der LSE 2010 abgestellt (Urteil 9C_808/2015 vom 29. Februar 2016 E. 3.5, in: SVR 2016 IV Nr. 21 S. 63). Vorliegend besteht bei einem Beschäftigungsgrad von 70 % auf der untersten Stufe der beruflichen Stellung somit kein Anlass für einen (zusätzlichen) Abzug.
3.3. Das kantonale Gericht erachtete sodann die lange Abwesenheit vom Arbeitsmarkt als abzugsrelevant, was von der Beschwerdeführerin ebenfalls zu Recht kritisiert wird. Diese betrifft das Kriterium der Dienstjahre, dessen Bedeutung gemäss der Rechtsprechung im privaten Sektor abnimmt, je niedriger das Anforderungsprofil ist (Urteil 9C_808/2015 vom 29. Februar 2016 E. 3.4.2, in: SVR 2016 IV Nr. 21 S. 62; Urteil 8C_351/2014 vom 14. August 2014 E. 5.2.4.2 mit Hinweis). Der Beschwerdegegner war vor seiner Berentung mehrere Jahre als Maschinenführer und anschliessend während rund zwei Jahren als Koch im familieneigenen Imbissstand tätig gewesen. Seit 2001 geht er keiner Erwerbstätigkeit mehr nach. Er verfügt über keine abgeschlossene Berufsausbildung. Für ihn kommen (im Rahmen des Zumutbarkeitsprofils) daher Hilfsarbeitertätigkeiten im untersten Kompetenzniveau in Betracht. Deshalb spielt hier das Kriterium der langen Abwesenheit vom Arbeitsmarkt nur eine unbedeutende Rolle und vermag einen Abzug nicht zu rechtfertigen.
3.4. Auch die weiteren Argumente, die der Beschwerdegegner ins Feld führt, sprechen nicht für einen Abzug:
3.4.1. Die vom Versicherten behaupteten Beschwerden, die seit der Begutachtung im Jahr 2007 aufgetreten seien, liessen sich gemäss den verbindlichen Feststellungen der Vorinstanz nicht bestätigen. Deshalb ändert sich nichts am im Dezember 2007 formulierten somatischen Zumutbarkeitsprofil. Darin sind die leidensbedingten (somatischen) Einschränkungen, einschliesslich des vermehrten Pausenbedarfs und der vermehrten Zeitaufwendungen für ärztliche und physiotherapeutische Massnahmen sowie für Muskeldetonisierungen, bereits enthalten. Diese dürfen daher im Rahmen eines allfälligen Abzugs nicht erneut berücksichtigt werden (vgl. Urteile 8C_12/2017 vom 28. Februar 2017 E. 5.5.1, 9C_846/2014 vom 22. Januar 2015 E. 4.1.1).
3.4.2. Sodann führt die gesundheitlich bedingte Unmöglichkeit, weiterhin körperlich schwere Arbeiten zu verrichten, nicht automatisch zu einer Verminderung des hypothetischen Invalidenlohns. Vielmehr ist der Umstand allein, dass nur mehr leichte bis mittelschwere Arbeiten zumutbar sind, auch bei eingeschränkter Leistungsfähigkeit kein Grund für einen zusätzlichen leidensbedingten Abzug, weil der Tabellenlohn im Kompetenzniveau 1 bereits eine Vielzahl von leichten und mittelschweren Tätigkeiten umfasst (Urteile 9C_455/2013 vom 4. Oktober 2013 E. 4.4; 9C_386/2012 vom 18. September 2012 E. 5.2).
3.4.3. Des Weiteren wirkt sich der Faktor Alter nicht (zwingend) lohnsenkend aus. Denn Hilfsarbeiten werden auf dem hypothetisch ausgeglichenen Arbeitsmarkt (<ref-law>) altersunabhängig nachgefragt (vgl. z.B. Urteile 9C_134/2016 vom 12. April 2016 E. 5.3; 8C_672/2013 vom 20. Februar 2014 E. 3.3).
3.4.4. Schliesslich lässt sich aus dem Umstand, dass die IV-Stelle in der Verfügung vom 9. Oktober 2008 einen Abzug von 15 % gewährte, nichts zu Gunsten des Beschwerdegegners ableiten, weil bei jeder Rentenbeurteilung über einen allfälligen Abzug neu zu befinden ist (Urteil 8C_463/2015 vom 24. September 2015 E. 3.1).
3.5. Nach dem Gesagten ist der von der Vorinstanz vorgenommene Abzug vom Tabellenlohn bundesrechtswidrig und nicht zu berücksichtigen. Der Invaliditätsgrad beläuft sich somit auf 30 %. Der Versicherte hat daher keinen Anspruch mehr auf eine Invalidenrente. Die Beschwerde ist begründet.
4.
Das Gesuch um Gewährung der aufschiebenden Wirkung wird mit dem Urteil in der Sache gegenstandslos.
5.
Dem Ausgang des Verfahrens entsprechend hat der Beschwerdegegner die Gerichtskosten zu tragen (<ref-law>). Eine Parteientschädigung ist nicht geschuldet (<ref-law>).

Demnach erkennt das Bundesgericht:
1.
Die Beschwerde wird gutgeheissen. Der Entscheid des Sozialversicherungsgerichts des Kantons Zürich vom 3. Oktober 2016 wird aufgehoben und die Verfügung der IV-Stelle des Kantons Zürich vom 11. Mai 2015 bestätigt.
2.
Die Gerichtskosten von Fr. 800.- werden dem Beschwerdegegner auferlegt.
3.
Die Sache wird zur Neuverlegung der Kosten und der Parteientschädigung des vorangegangenen Verfahrens an das Sozialversicherungsgericht des Kantons Zürich zurückgewiesen.
4.
Dieses Urteil wird den Parteien, dem Sozialversicherungsgericht des Kantons Zürich und dem Bundesamt für Sozialversicherungen schriftlich mitgeteilt.
Luzern, 22. März 2017
Im Namen der I. sozialrechtlichen Abteilung
des Schweizerischen Bundesgerichts
Der Präsident: Maillard
Die Gerichtsschreiberin: Betschart