ITCS welcomes both conceptual and technical contributions whose contents will advance and inspire the greater theory community. when coming from a more senior researcher to a less senior one. Vijayalakshmi Sarraju1, Jaya Pal2 and Supreeti Kamilya3, 1Department of Computer Science and Engineering, BIT Extension Centre Lalpur, 2Department of Computer Science and Engineering, BIT Extension Centre Lalpur, 3Department of Computer Science and Engineering, BIT Mesra. Authors: Elaine Shi, Hao Chung, Ke Wu (Carnegie Mellon University), The Complexity of Infinite-Horizon General-Sum Stochastic Games, Authors: Yujia Jin (Stanford University); Vidya Muthukumar (Georgia Institute of Technology); Aaron Sidford (Stanford University), Black-box Constructive Proofs are Unavoidable, Authors: Lijie Chen (UC Berkeley); Ryan Williams (MIT); Tianqi Yang (Tsinghua University), Authors: Mingda Qiao, Gregory Valiant (Stanford University), False Consensus, Information Theory, and Prediction Markets, Authors: Yuqing Kong (Peking University); Grant Schoenebeck (University of Michigan), Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence, Authors: Jason Gaitonde (Cornell University); Yingkai Li (Yale University); Bar Light (Microsoft Research New York City); Brendan Lucier (Microsoft Research New England); Aleksandrs Slivkins (Microsoft Research New York City), New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method, Recovery from Non-Decomposable Distance Oracles, Authors: Zhuangfei Hu (Unafilliated); Xinda Li (University of Waterloo); David Woodruff (Carnegie Mellon University); Hongyang Zhang, Shufan Zhang (University of Waterloo), On Identity Testing and Noncommutative Rank Computation over the Free Skew Field, Authors: V. Arvind (Institute of Mathematical Sciences (HBNI), Chennai); Abhranil Chatterjee (Indian Institute of Technology Bombay, India); Utsab Ghosal, Partha Mukhopadhyay (Chennai Mathematical Institute); Ramya C (Institute of Mathematical Sciences), Rigidity in Mechanism Design and its Applications, Authors: Shahar Dobzinski, Ariel Shaulker (Weizmann Institute), Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations, Authors: Anurag Anshu (Harvard University); Tony Metger (ETH Zurich), Secure Distributed Network Optimization Against Eavesdroppers, Authors: Yael Hitron, Merav Parter (Weizmann Institute); Eylon Yogev (Bar-Ilan University), Private Counting of Distinct and k-Occurring Items in Time Windows, Authors: Badih Ghazi, Ravi Kumar (Google); Pasin Manurangsi (Google Research); Jelani Nelson (UC Berkeley & Google Research), Authors: Omri Ben-Eliezer, Dan Mikulincer, Elchanan Mossel (MIT); Madhu Sudan (Harvard University), Authors: Mirza Ahad Baig (ISTA); Suvradip Chakraborty (ETH Zurich); Stefan Dziembowski (University of Warsaw and IDEAS NCBR); Magorzata Gazka (University of Warsaw); Tomasz Lizurej (University of Warsaw and IDEAS NCBR); Krzysztof Pietrzak (ISTA), Clustering Permutations: New Techniques with Streaming Applications, Authors: Diptarka Chakraborty (National University of Singapore); Debarati Das (Pennsylvania State University); Robert Krauthgamer (Weizmann Institute of Science), Authors: Sourav Chakraborty (Indian Statistical Institute (ISI) , Kolkata, India); Anna Gal (University of Texas at Austin); Sophie Laplante (Universit Paris Cit); Rajat Mittal (Indian Institute of Technology Kanpur); Anupa Sunny (Universit Paris Cit), The Strength of Equality Oracles in Communication, Authors: Toniann Pitassi (Columbia University); Morgan Shirley (University of Toronto); Adi Shraibman (The Academic College of Tel Aviv-Yaffo), Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments, Authors: Varun Gupta (University of Chicago); Ravishankar Krishnaswamy (Microsoft Research India); Sai Sandeep (Carnegie Mellon University); Janani Sundaresan (Rutgers University), A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit, Authors: Hamza Fawzi (University of Cambridge); Omar Fawzi (Inria, ENS de Lyon); Samuel Scalet (University of Cambridge), An Improved Lower Bound for Matroid Intersection Prophet Inequalities, Authors: Raghuvansh Saxena (Microsoft Research); Santhoshini Velusamy (Harvard University); S. Matthew Weinberg (Princeton University), Authors: Harry Buhrman (QuSoft, CWI, University of Amsterdam); Noah Linden (University of Bristol); Laura Maninska (University of Copenhagen); Ashley Montanaro (Phasecraft Ltd, University of Bristol); Maris Ozols (QuSoft, University of Amsterdam), Authors: Prahladh Harsha (TIFR, Mumbai); Daniel Mitropolsky (Columbia University); Alon Rosen (Bocconi University and Reichman University), Authors: Elette Boyle (Reichman University and NTT Research); Yuval Ishai (Technion); Pierre Meyer (Reichman University and IRIF, Universit Paris Cit, CNRS); Robert Robere (McGill); Gal Yehuda (Technion), Resilience of 3-Majority Dynamics to Non-Uniform Schedulers, Authors: Uri Meir, Rotem Oshman, Ofer Shayevitz, Yuval Volkov (Tel Aviv University), An Algorithmic Bridge Between Hamming and Levenshtein Distances, Authors: Elazar Goldenberg (The Academic College of Tel Aviv-Yaffo); Tomasz Kociumaka (Max Planck Institute for Informatics); Robert Krauthgamer (Weizmann Institute of Science); Barna Saha (University of California San Diego), Lifting to Parity Decision Trees via Stifling, Authors: Arkadev Chattopadhyay (TIFR, Mumbai); Nikhil S. Mande (CWI and QuSoft, Amsterdam); Swagato Sanyal (IIT Kharagpur); Suhail Sherif (Vector Institute, Toronto), Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly, Authors: Gillat Kol (Princeton University); Dmitry Paramonov (Princeton University); Raghuvansh Saxena (Microsoft Research); Huacheng Yu (Princeton University), Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds, Authors: Klim Efremenko (Ben-Gurion University); Gillat Kol, Dmitry Paramonov (Princeton University); Raghuvansh R. Saxena (Microsoft Research), Authors: Natalia Dobrokhotova-Maikova (Yandex, Moscow, Russia); Alexander Kozachinskiy (Institute for Mathematical and Computational Engineering, Universidad Catlica de Chile \ IMFD & CENIA Chile, Santiago, Chile); Vladimir Podolskii (Courant Institute of Mathematical Sciences, New York University, NY, USA), Algorithms with More Granular Differential Privacy Guarantees, Authors: Badih Ghazi, Ravi Kumar, Pasin Manurangsi, Thomas Steinke (Google Research), Bootstrapping Homomorphic Encryption via Functional Encryption, Authors: Nir Bitansky, Tomer Solomon (Tel Aviv University), Authors: Omrit Filtser (The Open University of Israel); Mayank Goswami (Queens College, City University of New York); Joseph Mitchell (Stony Brook University); Valentin Polishchuk (Linkoping University), Communication Complexity of Inner Product in Symmetric Normed Spaces, Authors: Jaroslaw Blasiok, Alexandr Andoni (Columbia University); Arnold Filtser (Bar Ilan University).
itcs 2022 accepted papers