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