# ITCS 2023 Accepted Papers

1. Rigidity for Monogamy-of-Entanglement Games

2. Opponent Indifference in Rating Systems: A Theoretical Case for Sonas

3. Online Learning and Bandits with Queried Hints

4. Improved Monotonicity Testing Over the Hypergrid via Hypercube Embedddings

5. Learning Reserve Prices in Second-Price Auctions

6. Symmetric Formulas for Products of Permutations

7. Asymptotically Tight Bounds on the Time Complexity of Broadcast and its Variants in Dynamic Networks

8. A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems

9. Strategyproof Scheduling with Predictions

10. Learning versus Pseudorandom Generators in Constant Parallel Time

11. Exact Completeness of LP Hierarchies for Linear Codes

12. Proofs of Quantumness from Trapdoor Permutations

13. Exponential separations using guarded extension variables

14. Quantum algorithms and the power of forgetting

15. On Interactive Proofs of Proximity with Proof-Oblivious Queries

16. Matrix multiplication via matrix groups

17. A New Conjecture on Hardness of Low-Degree 2-CSP’s with Implications to Hardness of Densest k-Subgraph and Other Problems

18. Making Decisions under Outcome Performativity

19. Loss Minimization through the lens of Outcome Indistinguishability

20. The Time Complexity of Consensus Under Oblivious Message Adversaries

21. Necessary Conditions in Multi-Server Differential Privacy

22. On Oracles and Algorithmic Methods for Proving Lower Bounds

23. Beyond Worst-Case Budget-Feasible Mechanism Design

24. Quantum space, ground space traversal, and how to embed multi-prover interactive proofs into unentanglement

25. Unitary property testing lower bounds by polynomials

26. Incompressiblity and Next-Block Pseudoentropy

27. PPP-Completeness and Extremal Combinatorics

28. Beeping Shortest Paths via Hypergraph Bipartite Decomposition

29. Expander Decomposition in Dynamic Streams

30. Fractional certificates for bounded functions

31. Extremal Combinatorics, iterated pigeonhole arguments, and generalizations of PPP

32. Depth-Bounded Quantum Cryptography with Applications to One-Time Memory and More

33. Kolmogorov Complexity Characterizes Statistical Zero Knowledge

34. Vertex Sparsification for Edge Connectivity in Polynomial Time

35. On the computational hardness needed for quantum cryptography

36. Random Max-CSPs Inherit Algorithmic Hardness from Spin Glasses

37. Rounding via Low Dimensional Embeddings

38. Certification with an NP Oracle

39. Unsplittable Euclidean Capacitated Vehicle Routing: A $(2+\epsilon)$-Approximation Algorithm

40. Efficient algorithms for certifying lower bounds on the discrepancy of random matrices

41. Matroid Partition Property and the Secretary Problem

42. A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators

43. Asynchronous Multi-Party Quantum Computation

44. Low-Stabilizer-Complexity Quantum States Are Not Pseudorandom

45. Karchmer-Wigderson Games for Hazard-free Computation

46. Improved Inapproximability of VC Dimension and Littlestone's Dimension via (Unbalanced) Biclique

47. Garland’s Technique for Posets and High Dimensional Grassmannian Expanders

48. Bit Complexity of Jordan Normal Form and Spectral Factorization

50. On computing homological hitting sets

51. Decision Making under Miscalibration

52. Graph Searching with Predictions

53. Making Auctions Robust to Aftermarkets

54. HappyMap: A Generalized Multicalibration Method

56. Worst-Case to Expander-Case Reductions

57. On disperser/lifting properties of the Index and Inner-Product functions

58. Counting Subgraphs in Somewhere Dense Graphs

59. Consensus Division in an Arbitrary Ratio

60. Quantum Proofs of Deletion for Learning with Errors

61. Differentially Private Continual Releases of Streaming Frequency Moment Estimations

62. Generalized Private Selection and Testing with High Confidence

63. Comparative Learning: A Sample Complexity Theory for Two Hypothesis Classes

64. List Agreement Expansion from Coboundary Expansion

65. TFNP Characterizations of Proof Systems and Monotone Circuits

66. All-Norm Load Balancing in Graph Streams via the Multiplicative Weights Update Method

67. What Can Cryptography Do For Decentralized Mechanism Design?

68. The Complexity of Infinite-Horizon General-Sum Stochastic Games

69. Black-box Constructive Proofs are Unavoidable

70. Online Pen Testing

71. False Consensus, Information Theory, and Prediction Markets

72. Budget Pacing in Repeated Auctions: Regret and Efficiency without Convergence

73. New Lower Bounds and Derandomization for ACC, and a Derandomization-centric View on the Algorithmic Method

74. Recovery from Non-Decomposable Distance Oracles

75. On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

76. Rigidity in Mechanism Design and its Applications

77. Concentration bounds for quantum states and limitations on the QAOA from polynomial approximations

78. Secure Distributed Network Optimization Against Eavesdroppers

79. Private Counting of Distinct and k-Occurring Items in Time Windows

80. Is This Correct? Let's Check!

81. Efficiently Testable Circuits

82. Clustering Permutations: New Techniques with Streaming Applications

83. Certificate games

84. The Strength of Equality Oracles in Communication

85. Look Before, Before You Leap: Online Vector Load Balancing with Few Reassignments

86. A subpolynomial-time algorithm for the free energy of one-dimensional quantum systems in the thermodynamic limit

87. An Improved Lower Bound for Matroid Intersection Prophet Inequalities

88. Quantum majority vote

89. Downward self-reducibility in TFNP

90. On Low-End Obfuscation and Learning

91. Resilience of 3-Majority Dynamics to Non-Uniform Schedulers

92. An Algorithmic Bridge Between Hamming and Levenshtein Distances

93. Lifting to Parity Decision Trees via Stifling

94. Characterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly

95. Noisy Radio Network Lower Bounds Via Noiseless Beeping Lower Bounds

96. Constant-depth sorting networks

97. Algorithms with More Granular Differential Privacy Guarantees

98. Bootstrapping Homomorphic Encryption via Functional Encryption

99. On Flipping the Fréchet distance

100. Communication Complexity of Inner Product in Symmetric Normed Spaces

101. Is it easier to count communities than find them?