Bounded simultaneous messages

DOI10.4230/LIPICS.FSTTCS.2023.23MaRDI QIDQ6951713zbMATH OpenFDO

Authors Andrej Bogdanov, Krishnamoorthy Dinesh, Yuval Filmus, Yuval Ishai, Avi Kaplan, Sruthi Sekar

Publication date 28 July 2025

Copyright license Creative Commons Attribution 4.0 International

zbMATH Keywords

lower boundsalgebraic degreepreprocessingsimultaneous messagesinstance hiding

Mathematics Subject Classification ID

Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Theory of computing (68Qxx)

Cites work

• scientific article; zbMATH DE number 4213418 (Why is no real title available?)
• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• scientific article; zbMATH DE number 697824 (Why is no real title available?)
• scientific article; zbMATH DE number 1512689 (Why is no real title available?)
• scientific article; zbMATH DE number 7561745 (Why is no real title available?)
• scientific article; zbMATH DE number 5485587 (Why is no real title available?)
• scientific article; zbMATH DE number 7788370 (Why is no real title available?)
• A $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ Algorithm for Certain NP-Complete Problems
• A cryptanalytic time-memory trade-off
• Boolean Circuits, Tensor Ranks, and Communication Complexity
• Bounded simultaneous messages
• Classical recursion theory. The theory of functions and sets of natural numbers.
• Communication Complexity of Simultaneous Messages
• Complexity Lower Bounds using Linear Algebra
• Computing Partitions with Applications to the Knapsack Problem
• Efficient fully homomorphic encryption from (standard) LWE
• Exponential lower bounds for depth three Boolean circuits
• Formula lower bounds via the quantum method
• Founding Cryptography on Oblivious Transfer – Efficiently
• Fully homomorphic encryption using ideal lattices
• Gaussian elimination is not optimal
• Graph Nonisomorphism Has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses
• Graph complexity
• Graph complexity and slice functions
• How to compute under \({\mathcal{AC}}^{0}\) leakage without secure hardware
• Improved bound for complexity of matrix multiplication
• Improving Schroeppel and Shamir’s algorithm for subset sum via orthogonal vectors
• Locally random reductions: Improvements and applications
• Natural proofs
• On Graph Complexity
• Pseudorandomness for approximate counting and sampling
• Rigorous Time/Space Trade-offs for Inverting Functions
• Rounds in Communication Complexity Revisited
• Superpolynomial size set-systems with restricted intersections mod 6 and explicit Ramsey graphs
• The complexity of DNF of parities

Cited in

(1)

• Bounded simultaneous messages

This page was built for publication: Bounded simultaneous messages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6951713)