5 citations · 5 across the 5 of their papers we have counts for
5 papers
Report on the First HIPstIR Workshop on the Future of Information Retrieval
Laura Dietz, Bhaskar Mitra, Jeremy Pickens +21
The vision of HIPstIR is that early stage information retrieval (IR) researchers get together to develop a future for non-mainstream ideas and research agendas in IR. The first ite…
Element Distinctness, Frequency Moments, and Sliding Windows
Paul Beame, Raphael Clifford, Widad Machmouchi
We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistic…
Sliding Windows with Limited Storage
Paul Beame, Raphael Clifford, Widad Machmouchi
We consider time-space tradeoffs for exactly computing frequency moments and order statistics over sliding windows. Given an input of length 2n-1, the task is to output the functio…
Local-Testability and Self-Correctability of q-ary Sparse Linear Codes
Widad Machmouchi
We prove that q-ary sparse codes with small bias are self-correctable and locally testable. We generalize a result of Kaufman and Sudan that proves the local testability and correc…
The Quantum Query Complexity of AC0
Paul Beame, Widad Machmouchi
We show that any quantum algorithm deciding whether an input function from to is 2-to-1 or almost 2-to-1 requires queries to . The same lower bound holds…