ANR support

All related publications need to mention the support from the project as follows:
Supported by the French ANR Blanc project ANR-12-BS02-005 (RDAM)

List of publications

Refereed Articles
[1] Solving systems of diagonal polynomial equations over finite fields. (Gábor Ivanyos, Miklos Santha), In Theor. Comput. Sci., volume 657, 2017. [bib]
[2] Improved Quantum Query Algorithms for Triangle Detection and Associativity Testing. (Troy Lee, Frédéric Magniez, Miklos Santha), In Algorithmica, volume 77, 2017. [bib]
[3] Relative Discrepancy Does Not Separate Information and Communication Complexity (Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland), In ACM Tans. on Computation Theory, volume 9, 2016. [bib]
[4] Approximate consistency for transformations on words and trees. (Michel de Rougemont, Adrien Vieilleribière), In Theor. Comput. Sci., volume 626, 2016. [bib]
[5] Approximating Semi-matchings in Streaming and in Two-Party Communication. (Christian Konrad, Adi Rosén), In ACM Trans. Algorithms, volume 12, 2016. [bib]
[6] Information cost of quantum communication protocols. (Iordanis Kerenidis, Mathieu Laurière, Francois Le Gall, Mathys Rennela), In Quantum Information & Computation, volume 16, 2016. [bib]
[7] Clique Here: On the Distributed Complexity in Fully-Connected Networks. (Benny Applebaum, Dariusz R. Kowalski, Boaz Patt-Shamir, Adi Rosén), In Parallel Processing Letters, volume 26, 2016. [bib]
[8] Quantum Walks Can Find a Marked Element on Any Graph. (Hari Krovi, Frédéric Magniez, Maris Ozols, Jérémie Roland), In Algorithmica, volume 74, 2016. [bib]
[9] Improving Quantum Query Complexity of Boolean Matrix Multiplication Using Graph Collision. (Stacey Jeffery, Robin Kothari, François Le Gall, Frédéric Magniez), In Algorithmica, volume 76, 2016. [bib]
[10] Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems. (Pierre Fraigniaud, Magnús M. Halldórsson, Boaz Patt-Shamir, Dror Rawitz, Adi Rosén), In Algorithmica, volume 74, 2016. [bib]
[11] Space-Constrained Interval Selection (Yuval Emek, Magnús M. Halldórsson, Adi Rosén), In ACM Transactions on Algorithms, 2016. (Accepted for publication) [bib]
[12] Optimal Parallel Quantum Query Algorithms (Stacey Jeffery, Frederic Magniez, Ronald de Wolf), In Algorithmica, Springer Nature, 2016. [bib]
[13] Semi-Streaming Set Cover (Yuval Emek, Adi Rosén), In ACM Trans. Algorithms, Association for Computing Machinery (ACM), volume 13, 2016. [bib]
[14] Improved bounds for the randomized decision tree complexity of recursive majority (F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, D. Xiao), In Random Structures & Algorithms, 2015. (To appear) [bib]
[15] Discrete systolic inequalities and decompositions of triangulated surfaces (Éric Colin de Verdière, Alfredo Hubard, Arnaud de Mesmay), In Discrete & Computational Geometry, volume 53, 2015. [bib]
[16] A simpler proof of existence of quantum weak coin flipping with arbitrarily small bias (Dorit Aharonov, André Chailloux, Maor Ganz, Iordanis Kerenidis, Loïck Magnin), In SIAM Journal of Computing (to appear), arXiv preprint arXiv:1402.7166, 2015. [bib]
[17] Nonlocality and conflicting interest games (A. Pappa, N. Kumar, T. Lawson, M. Santha, S. Zhang, E. Diamanti, I. Kerenidis), In Physical Review Letters, volume 112, 2015. [bib]
[18] Constructing near spanning trees with few local inspections (Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira), In Random Struct. Algorithms, volume 50, 2015. [bib]
[19] Generalized Wong sequences and their applications to Edmonds' problems (G. Ivanyos, M. Karpinski, Y. Qiao, M. Santha), In Journal of Computer and System Sciences, volume 81, 2015. [bib]
[20] A Local Algorithm for Generating Preferential Attachment Graphs (Guy Even, Reut Levi, Moti Medina, Adi Rosén), In Unpublished manuscript, 2015. [bib]
[21] A nonmonotone analysis with the primal-dual approach: Online routing of virtual circuits with unknown durations (Guy Even, Moti Medina), In Theor. Comput. Sci., volume 584, 2015. [bib]
[22] Experimental plug and play quantum coin flipping (Anna Pappa, Paul Jouguet, Thomas Lawson, André Chailloux, Matthieu Legré, Patrick Trinkler, Iordanis Kerenidis, Eleni Diamanti), In Nature communications, Nature Publishing Group, volume 5, 2014. [bib]
[23] Recognizing well-parenthesized expressions in the streaming model (F. Magniez, C. Mathieu, A. Nayak), In SIAM Journal on Computing, volume 43, 2014. (Joint IRIF/DIENS publication) [bib]
[24] Privacy in quantum communication complexity (Iordanis Kerenidis, Mathieu Lauriere, François Le Gall, Mathys Rennela), In arXiv preprint arXiv:1409.8488, 2014. [bib]
[25] Hidden translation and orbit coset in quantum computing (K. Friedl, G. Ivanyos, F. Magniez, M. Santha, P. Sen), In SIAM Journal on Computing, volume 43, 2014. [bib]
[26] Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses (H. Dell, D. van Melkebeek), In Journal of ACM, volume 61, 2014. [bib]
[27] Exponential time complexity of the permanent and the Tutte polynomial (Holger Dell, Thore Husfeldt, Dániel Marx, Nina Taslaman, Martin Wahlén), In Transactions on Algorithms, volume 10, 2014. [bib]
[28] Lower bounds on information complexity via zero-communication protocols and applications (I. Kerenidis, S. Laplante, V. Lerays, J. Roland, D. Xiao), In SIAM Journal on Computing, 2014. (Special issue for FOCS 2012. To appear) [bib]
[29] Polynomial time quantum algorithms for certain bivariate hidden polynomial problems (T. Decker, P. Høyer, G. Ivanyos, M. Santha), In Quantum Information and Computation, volume 14, 2014. [bib]
[30] Testing graph isotopy on surfaces (E. Colin de Verdière, A. de Mesmay), In Discrete & Computational Geometry, volume 51, 2014. [bib]
[31] Strong connections between quantum encodings, nonlocality, and cryptography (A. Chailloux, I. Kerenidis, J. Sikora), In Physical Review A, volume 89, 2014. [bib]
[32] Quantum commitments from complexity assumptions (A. Chailloux, I. Kerenidis, B. Rosgen), In Computational Complexity, 2014. (To appear) [bib]
[33] Validating XML documents in the streaming model with external memory (C. Konrad, F. Magniez), In ACM Transactions on Database Systems, volume 38, 2013. (Special issue of ICDT'12) [bib]
[34] The min mean-weight cycle in a random network (C. Mathieu, D. Wilson), In Combinatorics, Probability & Computing, volume 22, 2013. [bib]
[35] QMA variants with polynomially many provers (S. Gharibian, J. Sikora, S. Upadhyay), In Journal of Quantum Information and Computation, volume 13, 2013. [bib]
[36] Hidden symmetry subgroup problem (T. Decker, G. Ivanyos, M. Santha, P. Wocjan), In SIAM Journal on Computing, volume 42, 2013. [bib]
[37] Lower bounds for quantum oblivious transfer (A. Chailloux, I. Kerenidis, J. Sikora), In Journal of Quantum Information and Computation, volume 13, 2013. [bib]
[38] Stochastic Cellular Automata: Correlations, Decidability and Simulations (P. Arrighi, N. Schabanel, G. Theyssier), In Fundamenta Informaticae, volume 126, 2013. [bib]
Refereed Conference Papers
[39] Provably secure key establishment against quantum adversaries (Alexandrs Belovs, Gilles Brassard, Peter Høyer, Marc Kaplan, Sophie Laplante, Louis Salvail), In 12nd Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2017, June 14-16, 2017, Paris, France, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib]
[40] Extended Learning Graphs for Triangle Finding. (Titouan Carette, Mathieu Laurière, Frédéric Magniez), In 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 66, 2017. [bib]
[41] Quantum recommendation systems (Iordanis Kerenidis, Anupam Prakash), In Proceedings of the 2017 Conference on Innovations in Theoretical Computer Science, ITCS'17, Berkeley, CA, USA, January 9-11, 2017, ACM, 2017. [bib]
[42] Sublinear Random Access Generators for Preferential Attachment Graphs (Guy Even, Reut Levi, Moti Medina, Adi Rosén), In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib]
[43] Streaming Communication Protocols (Lucas Boczkowski, Iordanis Kerenidis, Frédéric Magniez), In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib]
[44] On the Polynomial Parity Argument complexity of the Combinatorial Nullstellensatz (Alexandrs Belovs, Gábor Ivanyos, Youming Qiao, Miklos Santha, Siyi Yang), In 32nd Conference on Computational Complexity, CCC 2017, July 6-9, 2017, Riga, Latvia, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. [bib]
[45] Non-local Probes Do Not Help with Many Graph Problems. (Mika Göös, Juho Hirvonen, Reut Levi, Moti Medina, Jukka Suomela), In , 2016. [bib]
[46] Robust Bell Inequalities from Communication Complexity. (Sophie Laplante, Mathieu Laurière, Alexandre Nolin, Jérémie Roland, Gabriel Senno), In 11th Conference on the Theory of Quantum Computation, Communication and Cryptography, TQC 2016, September 27-29, 2016, Berlin, Germany, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 61, 2016. [bib]
[47] Separations in query complexity based on pointer functions. (Andris Ambainis, Kaspars Balodis, Aleksandrs Belovs, Troy Lee, Miklos Santha, Juris Smotrovs), In Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, ACM, 2016. [bib]
[48] Multi-Party Protocols, Information Complexity and Privacy. (Iordanis Kerenidis, Adi Rosén, Florent Urrutia), In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 58, 2016. [bib]
[49] On the Complexity of Probabilistic Trials for Hidden Satisfiability Problems. (Itai Arad, Adam Bouland, Daniel Grier, Miklos Santha, Aarthi Sundaram, Shengyu Zhang), In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, August 22-26, 2016 - Kraków, Poland, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 58, 2016. [bib]
[50] Linear Time Algorithm for Quantum 2SAT. (Itai Arad, Miklos Santha, Aarthi Sundaram, Shengyu Zhang), In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2016. [bib]
[51] Separations in Communication Complexity Using Cheat Sheets and Information Complexity. (Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee, Miklos Santha), In IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, New Brunswick, New Jersey, USA, 9-11 October 2016, IEEE Computer Society, 2016. [bib]
[52] Unconditionally Secure Computation with Reduced Interaction. (Ivan Damgård, Jesper Buus Nielsen, Rafail Ostrovsky, Adi Rosén), In Advances in Cryptology - EUROCRYPT 2016 - 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II, Springer, volume 9666, 2016. [bib]
[53] Online Budgeted Maximum Coverage. (Dror Rawitz, Adi Rosén), In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 57, 2016. [bib]
[54] Streaming Property Testing of Visibly Pushdown Languages. (Nathanaël François, Frédéric Magniez, Michel de Rougemont, Olivier Serre), In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 57, 2016. [bib]
[55] A Constant Approximation Algorithm for Scheduling Packets on Line Networks. (Guy Even, Moti Medina, Adi Rosén), In 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 57, 2016. [bib]
[56] Stable Matching with Evolving Preferences. (Varun Kanade, Nikos Leonardos, Frédéric Magniez), In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, volume 60, 2016. [bib]
[57] Approximating connectivity domination in weighted bounded-genus graphs (Vincent Cohen-Addad, Éric Colin de Verdière, Philip N. Klein, Claire Mathieu, David Meierfrankenfeld), In Proceedings of the 48th Annual ACM Symposium on Theory of Computing (STOC), 2016. (To appear) [bib]
[58] Distance in the Forest Fire Model How far are you from Eve? (Varun Kanade, Reut Levi, Zvi Lotker, Frederik Mallmann-Trenn, Claire Mathieu), In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016, 2016. (Joint IRIF/DIENS publication) [bib]
[59] The value of analytical queries on Social Networks (M. de Rougemont, G. Vimont), In 2015 IEEE International Big Data Conference, MBD-SONET, 2015. [bib]
[60] The First-Order Contiguity of Sparse Random Graphs with Prescribed Degrees (N. Lefevre), In Theory and Applications of Models of Computation, Volume 9076 of the series Lecture Notes in Computer Science, 2015. [bib]
[61] QMA with subset state witnesses (Alex Bredariol Grilo, Iordanis Kerenidis, Jamie Sikora), In Mathematical Foundations of Computer Science 2015, 2015. [bib]
[62] New Constructions for Quantum Money (Marios Georgiou, Iordanis Kerenidis), In LIPIcs-Leibniz International Proceedings in Informatics, volume 44, 2015. [bib]
[63] Communication complexity of conditional disclosure of secrets and attribute-based encryption (Romain Gay, Iordanis Kerenidis, Hoeteck Wee), In Advances in Cryptology--CRYPTO 2015, 2015. [bib]
[64] Relative discrepancy does not separate information and communication complexity (Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Lauriere, Jérémie Roland), In International Colloquium on Automata, Languages, and Programming, 2015. [bib]
[65] A fixed parameter tractable approximation scheme for the optimal cut graph of a surface (Vincent Cohen-Addad, Arnaud de Mesmay), In Proceedings of the 23rd European Symposium on Algorithms (ESA), 2015. [bib]
[66] Multicuts in planar and bounded-genus graphs with bounded number of terminals (Éric Colin de Verdière), In Proceedings of the 23rd European Symposium on Algorithms (ESA), 2015. [bib]
[67] Correlation Clustering and Two-edge-connected Augmentation for Planar Graphs (Philip N. Klein, Claire Mathieu, Hang Zhou), In 32nd International Symposium on Theoretical Aspects of Computer Science, STACS 2015, March 4-7, 2015, Garching, Germany, 2015. [bib]
[68] Near-Linear Query Complexity for Graph Inference (Sampath Kannan, Claire Mathieu, Hang Zhou), In Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I, 2015. [bib]
[69] Separating decision tree complexity from subcube partition complexity (R. Kothari, D. Racicot-Desloges, M. Santha), In Proceedings of 19th International Workshop on Randomization and Computation, 2015. [bib]
[70] On solving systems of diagonal polynomial equations over finite fields (G. Ivanyos, M. Santha), In Proceedings of 9th International Frontiers of Algorithmics Workshop, 2015. [bib]
[71] Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees (Reut Levi, Ronitt Rubinfeld, Anak Yodpinyanee), In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, 2015. [bib]
[72] Better Deterministic Online Packet Routing on Grids (Guy Even, Moti Medina, Boaz Patt-Shamir), In Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, SPAA 2015, Portland, OR, USA, June 13-15, 2015, 2015. [bib]
[73] Distributed Maximum Matching in Bounded Degree Graphs (Guy Even, Moti Medina, Dana Ron), In Proceedings of the 2015 International Conference on Distributed Computing and Networking, ICDCN 2015, Goa, India, January 4-7, 2015, 2015. [bib]
[74] Effectiveness of Local Search for Geometric Optimization (Vincent Cohen-Addad, Claire Mathieu), In 31st International Symposium on Computational Geometry, SoCG 2015, June 22-25, 2015, Eindhoven, The Netherlands, 2015. [bib]
[75] Homophily and the Glass Ceiling Effect in Social Networks (Chen Avin, Barbara Keller, Zvi Lotker, Claire Mathieu, David Peleg, Yvonne Anne Pignolet), In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, 2015. (Joint IRIF/DIENS publication) [bib]
[76] Efficient universal computation by molecular co-transcriptional folding (Short announcement) (Cody Geary, Pierre-Étienne Meunier, Nicolas Schabanel, Shinnosuke Seki), In DNA21, 2015. [bib]
[77] StatsReduce in the cloud for approximate Analytics (Michel de Rougemont), In IEEE International Conference on Data Science and Advanced Analytics, DSAA 2014, Shanghai, China, 2014. [bib]
[78] Optimal parallel quantum query algorithms (S. Jeffery, F. Magniez, R. de Wolf), In Proceedings of 22nd European Symposium on Algorithms, 2014. [bib]
[79] Unidirectional Input/Output Streaming Complexity of Reversal and Sorting (N. François, R. Jain, F. Magniez), In Proceedings of 18th International Workshop on Randomization and Computation, 2014. [bib]
[80] AND-compression of NP-complete problems: Streamlined proof and minor observations (Holger Dell), In Proceedings of 9th International Symposium on Parameterized and Exact Computation, 2014. [bib]
[81] Redrawing the boundaries on purchasing data from privacy-sensitive individuals (K. Nissim, S. Vadhan, D. Xiao), In Proceedings of 5th Innovations in Theoretical Computer Science, 2014. [bib]
[82] First come first served for online slot allocation and huffman coding (M. Khare, C. Mathieu, N. Young), In Proceedings of the 25th Symposium on Discrete Algorithms, 2014. [bib]
[83] On the complexity of trial and error for constraint satisfaction problems (G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha, A. Sundaram), In Proceedings of 41st International Colloquium on Automata, Languages and Programming, 2014. (To appear) [bib]
[84] Generalized Wong sequences and their applications to Edmonds' problems (G. Ivanyos, M. Karpinski, Y. Qiao, M. Santha), In Proceedings of 31st Symposium on Theoretical Aspects of Computer Science, 2014. [bib]
[85] Sample Complexity Bounds on Differentially Private Learning via Communication Complexity (V. Feldman, D. Xiao), In Proceedings of 27th Annual Conference on Learning Theory, 2014. [bib]
[86] Semi-Streaming Set Cover (Y. Emek, A. Rosén), In Proceedings of 41st International Colloquium on Automata, Languages and Programming, 2014. [bib]
[87] Facility Location in Evolving Metrics (D. Eisenstat, C. Mathieu, N. Schabanel), In Proceedings of 41st International Colloquium on Automata, Languages and Programming, 2014. (Joint IRIF/DIENS publication) [bib]
[88] Approximating $k$-center in planar graphs (D. Eisenstat, P. Klein, C. Mathieu), In Proceedings of the 25th Symposium on Discrete Algorithms, 2014. [bib]
[89] An efficient quantum algorithm for finding hidden parabolic subgroups in the general linear group (T. Decker, G. Ivanyos, R. Kulkarni, Y. Qiao, M. Santha), In Proceedings of 39th International Symposium on Mathematical Foundations of Computer Science, 2014. [bib]
[90] Optimal bounds for parity-oblivious random access codes with applications (A. Chailloux, I. Kerenidis, S. Kundu, J. Sikora), In Proceedings of 9th Conference on the Theory of Quantum Computation, Communication and Cryptography, 2014. (To appear) [bib]
[91] Discrete systolic inequalities and decompositions of triangulated surfaces (E. Colin de Verdière, A. Hubard, A. de Mesmay), In Proceedings of 30th Annual Symposium on Computational Geometry, 2014. [bib]
[92] On the complexity of immersed normal surfaces (B. Burton, E. Colin de Verdière, A. de Mesmay), In Proceedings of the 30th European Workshop on Computational Geometry, 2014. (To appear) [bib]
[93] Improved quantum query algorithms for triangle finding and associativity testing (T. Lee, F. Magniez, M. Santha), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, 2013. [bib]
[94] Nested quantum walks with quantum data structures (S. Jeffery, R. Kothari, F. Magniez), In Proceedings of 24th ACM-SIAM Symposium on Discrete Algorithms, 2013. [bib]
[95] Streaming complexity of checking priority queues (N. François, F. Magniez), In Proceedings of 30th Symposium on Theoretical Aspects of Computer Science, 2013. [bib]
[96] Time-Efficient Quantum Walks for 3-Distinctness (A. Belovs, A. Childs, S. Jeffery, R. Kothari, F. Magniez), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. [bib]
[97] Is privacy compatible with truthfulness? (D. Xiao), In Proceedings of 4th Innovations in Theoretical Computer Science, 2013. [bib]
[98] Approximation of Large Probabilistic Networks by Structured Population Protocols (M. de Rougemont, M. Tracol), In Algebraic Informatics - 5th International Conference, CAI, 2013. [bib]
[99] Languages with Efficient Zero-Knowledge PCPs are in SZK (M. Mahmoody, D. Xiao), In Proceedings of 10th Theory of Cryptography Conference, 2013. [bib]
[100] Sublinear-time algorithms for monomer-dimer systems on bounded degree graphs (M. Lelarge, H. Zhou), In Proceedings of 24th International Symposium on Algorithms and Computation, 2013. [bib]
[101] Query complexity of matroids (R. Kulkarni, M. Santha), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. [bib]
[102] Approximating Semi-matchings in Streaming and in Two-Party Communication (C. Konrad, A. Rosén), In Proceedings of 40th International Colloquium on Automata, Languages and Programming, 2013. [bib]
[103] New lower bounds for privacy in communication protocols (I. Kerenidis, M. Laurière, D. Xiao), In Proceedings of 7th International Conference on Information Theoretic Security, 2013. [bib]
[104] Shrinking Maxima, Decreasing Costs: New Online Packing and Covering Problems (P. Fraigniaud, M. Halldórsson, B. Patt-Shamir, D. Rawitz, A. Rosén), In Proceedings of 16th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, 2013. [bib]
[105] Reordering Buffer Management with Advice (A. Adamaszek, M. Renault, A. Rosén, R van Stee), In Proceedings of 11th Workshop on Approximation and Online Algorithms, 2013. [bib]
Other Publications
[106] Computational topology of graphs on surfaces (Éric Colin de Verdière), Chapter in Handbook of Discrete and Computational Geometry (Jacob E. Goodman, Joseph O'Rourke, eds.), CRC Press LLC, 2016. (To appear) [bib]
[107] La physique quantique réinvente les algorithmes (I. Kerenidis, F. Magniez), Chapter in La Recherche, volume 501, 2015. [bib]
[108] Quantum and randomized query complexities (M. Santha), Chapter in Proceedings of 12th International Conference on Theory and Applications of Models of Computation, 2015. (Invited talk) [bib]
[109] Les hottes du Père Noël (Nicolas Schabanel), Chapter in 1024 -- Bulletin de la société informatique de France, Société Informatique de France, 2015. [bib]
[110] La médiation en informatique vue par le CNRS (Laure Guion, Nicolas Schabanel), Chapter in 1024 -- Bulletin de la société informatique de France, Société Informatique de France, 2015. [bib]
[111] De la carte au territoire ? (Éric Colin de Verdière, Arnaud de Mesmay), Chapter in Images des mathématiques, CNRS, 2014. [bib]
Powered by bibtexbrowser