Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds (English)
Free access
- New search for: Chakraborty, Sourav
- New search for: Ghosh, Arijit
- New search for: Mishra, Gopinath
- New search for: Sen, Sayantan
- New search for: Chakraborty, Sourav
- New search for: Ghosh, Arijit
- New search for: Mishra, Gopinath
- New search for: Sen, Sayantan
- New search for: Wootters, Mary
- Further information on Wootters, Mary:
- https://orcid.org/0000-0002-2345-2531
- New search for: Sanità, Laura
- Further information on Sanità, Laura:
- https://orcid.org/0000-0002-6384-1857
In:
LIPIcs, Volume 207, APPROX/RANDOM 2021
: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)
;
207
;
34:1-34:23
;
2021
-
ISBN:
-
ISSN:
- Conference paper / Electronic Resource
-
Title:Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication Worlds
-
Contributors:Chakraborty, Sourav ( author ) / Ghosh, Arijit ( author ) / Mishra, Gopinath ( author ) / Sen, Sayantan ( author ) / Wootters, Mary ( editor ) / Sanità, Laura ( editor )
-
Published in:LIPIcs, Volume 207, APPROX/RANDOM 2021 : Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) ; 207 ; 34:1-34:23Leibniz International Proceedings in Informatics (LIPIcs) ; 207 ; 34:1-34:23
-
Publisher:
- New search for: Schloss Dagstuhl – Leibniz-Zentrum für Informatik
-
Publication date:2021-09-15
-
Size:23 pages , 953259 byte
-
Remarks:LIPIcs, Vol. 207, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021), pages 34:1-34:23
-
ISBN:
-
ISSN:
-
DOI:
-
Type of media:Conference paper
-
Type of material:Electronic Resource
-
Language:English
-
Keywords:
-
Licence:
-
Source:
Table of contents conference proceedings
The tables of contents are generated automatically and are based on the data records of the individual contributions available in the index of the TIB portal. The display of the Tables of Contents may therefore be incomplete.
- 1
-
On Approximate Envy-Freeness for Indivisible Chores and Mixed ResourcesBhaskar, Umang / Sricharan, A. R. / Vaish, Rohit et al. | 2021
- 2
-
Optimal Algorithms for Online b-Matching with Variable Vertex CapacitiesAlbers, Susanne / Schubert, Sebastian et al. | 2021
- 3
-
Bag-Of-Tasks Scheduling on Related MachinesGupta, Anupam / Kumar, Amit / Singla, Sahil et al. | 2021
- 4
-
Hardness of Approximation for Euclidean k-MedianBhattacharya, Anup / Goyal, Dishant / Jaiswal, Ragesh et al. | 2021
- 5
-
Online Directed Spanners and Steiner ForestsGrigorescu, Elena / Lin, Young-San / Quanrud, Kent et al. | 2021
- 6
-
Query Complexity of Global Minimum CutBishnu, Arijit / Ghosh, Arijit / Mishra, Gopinath / Paraashar, Manaswi et al. | 2021
- 7
-
A Constant-Factor Approximation for Weighted Bond CoverKim, Eun Jung / Lee, Euiwoong / Thilikos, Dimitrios M. et al. | 2021
- 8
-
Truly Asymptotic Lower Bounds for Online Vector Bin PackingBalogh, János / Cohen, Ilan Reuven / Epstein, Leah / Levin, Asaf et al. | 2021
- 9
-
Fine-Grained Completeness for Optimization in PBringmann, Karl / Cassis, Alejandro / Fischer, Nick / Künnemann, Marvin et al. | 2021
- 10
-
An Estimator for Matching Size in Low Arboricity Graphs with Two ApplicationsJowhari, Hossein et al. | 2021
- 11
-
An Optimal Algorithm for Triangle Counting in the StreamJayaram, Rajesh / Kallaugher, John et al. | 2021
- 12
-
Matching Drivers to Riders: A Two-Stage Robust ApproachHousni, Omar El / Goyal, Vineet / Hanguir, Oussama / Stein, Clifford et al. | 2021
- 13
-
Secretary Matching Meets Probing with CommitmentBorodin, Allan / MacRury, Calum / Rakheja, Akash et al. | 2021
- 14
-
Semi-Streaming Algorithms for Submodular Function Maximization Under b-Matching ConstraintHuang, Chien-Chung / Sellier, François et al. | 2021
- 15
-
General Knapsack Problems in a Dynamic SettingFairstein, Yaron / Kulik, Ariel / Naor, Joseph (Seffi) / Raz, Danny et al. | 2021
- 16
-
Min-Sum Clustering (With Outliers)Banerjee, Sandip / Ostrovsky, Rafail / Rabani, Yuval et al. | 2021
- 17
-
Streaming Approximation Resistance of Every Ordering CSPSinger, Noah / Sudan, Madhu / Velusamy, Santhoshini et al. | 2021
- 18
-
Upper and Lower Bounds for Complete Linkage in General Metric SpacesArutyunova, Anna / Großwendt, Anna / Röglin, Heiko / Schmidt, Melanie / Wargalla, Julian et al. | 2021
- 19
-
On Two-Pass Streaming Algorithms for Maximum Bipartite MatchingKonrad, Christian / Naidu, Kheeran K. et al. | 2021
- 20
-
Approximation Algorithms for Demand Strip PackingGálvez, Waldo / Grandoni, Fabrizio / Ameli, Afrouz Jabal / Khodamoradi, Kamyar et al. | 2021
- 21
-
Peak Demand Minimization via Sliced Strip PackingDeppert, Max A. / Jansen, Klaus / Khan, Arindam / Rau, Malin / Tutas, Malte et al. | 2021
- 22
-
Tight Approximation Algorithms For Geometric Bin Packing with Skewed ItemsKhan, Arindam / Sharma, Eklavya et al. | 2021
- 23
-
Approximating Two-Stage Stochastic Supplier ProblemsBrubach, Brian / Grammel, Nathaniel / Harris, David G. / Srinivasan, Aravind / Tsepenekas, Leonidas / Vullikanti, Anil et al. | 2021
- 24
-
Fast Approximation Algorithms for Bounded Degree and Crossing Spanning Tree ProblemsChekuri, Chandra / Quanrud, Kent / Torres, Manuel R. et al. | 2021
- 25
-
Hitting Weighted Even Cycles in Planar GraphsGöke, Alexander / Koenemann, Jochen / Mnich, Matthias / Sun, Hao et al. | 2021
- 26
-
Revenue Maximization in Transportation NetworksBhawalkar, Kshipra / Kollias, Kostas / Purohit, Manish et al. | 2021
- 27
-
Connected k-Partition of k-Connected Graphs and c-Claw-Free GraphsBorndörfer, Ralf / Casel, Katrin / Issac, Davis / Niklanovits, Aikaterini / Schwartz, Stephan / Zeif, Ziena et al. | 2021
- 28
-
Better Pseudodistributions and Derandomization for Space-Bounded ComputationHoza, William M. et al. | 2021
- 29
-
On the Hardness of Average-Case k-SUMBrakerski, Zvika / Stephens-Davidowitz, Noah / Vaikuntanathan, Vinod et al. | 2021
- 30
-
Improved Hitting Set for Orbit of ROABPsBhargava, Vishwas / Ghosh, Sumanta et al. | 2021
- 31
-
A New Notion of Commutativity for the Algorithmic Lovász Local LemmaHarris, David G. / Iliopoulos, Fotis / Kolmogorov, Vladimir et al. | 2021
- 32
-
From Coupling to Spectral Independence and Blackbox Comparison with the Down-Up WalkLiu, Kuikui et al. | 2021
- 33
-
Singularity of Random Integer Matrices with Large EntriesKaringula, Sankeerth Rao / Lovett, Shachar et al. | 2021
- 34
-
Interplay Between Graph Isomorphism and Earth Mover’s Distance in the Query and Communication WorldsChakraborty, Sourav / Ghosh, Arijit / Mishra, Gopinath / Sen, Sayantan et al. | 2021
- 35
-
The Product of Gaussian Matrices Is Close to GaussianLi, Yi / Woodruff, David P. et al. | 2021
- 36
-
Fast Mixing via Polymers for Random Graphs with Unbounded DegreeGalanis, Andreas / Goldberg, Leslie Ann / Stewart, James et al. | 2021
- 37
-
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity LemmaServedio, Rocco A. / Tan, Li-Yang et al. | 2021
- 38
-
Improved Product-Based High-Dimensional ExpandersGolowich, Louis et al. | 2021
- 39
-
Improved Bounds for Coloring Locally Sparse HypergraphsIliopoulos, Fotis et al. | 2021
- 40
-
Smoothed Analysis of the Condition Number Under Low-Rank PerturbationsShah, Rikhav / Silwal, Sandeep et al. | 2021
- 41
-
Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-DecisionGhosh, Sumanta / Gurjar, Rohit et al. | 2021
- 42
-
On the Probabilistic Degree of an n-Variate Boolean FunctionSrinivasan, Srikanth / Venkitesh, S. et al. | 2021
- 43
-
The Swendsen-Wang Dynamics on TreesBlanca, Antonio / Chen, Zongchen / Štefankovič, Daniel / Vigoda, Eric et al. | 2021
- 44
-
Distance Estimation Between Unknown Matrices Using Sublinear Projections on Hamming CubeBishnu, Arijit / Ghosh, Arijit / Mishra, Gopinath et al. | 2021
- 45
-
Decision Tree Heuristics Can Fail, Even in the Smoothed SettingBlanc, Guy / Lange, Jane / Qiao, Mingda / Tan, Li-Yang et al. | 2021
- 46
-
On the Structure of Learnability Beyond P/PolyRajgopal, Ninad / Santhanam, Rahul et al. | 2021
- 47
-
The Critical Mean-Field Chayes-Machta DynamicsBlanca, Antonio / Sinclair, Alistair / Zhang, Xusheng et al. | 2021
- 48
-
On the Robust Communication Complexity of Bipartite MatchingAssadi, Sepehr / Behnezhad, Soheil et al. | 2021
- 49
-
L1 Regression with Lewis Weights SubsamplingParulekar, Aditya / Parulekar, Advait / Price, Eric et al. | 2021
- 50
-
Hitting Sets for Orbits of Circuit Classes and Polynomial FamiliesSaha, Chandan / Thankey, Bhargav et al. | 2021
- 51
-
Sampling Multiple Edges EfficientlyEden, Talya / Mossel, Saleet / Rubinfeld, Ronitt et al. | 2021
- 52
-
Lower Bounds for XOR of ForrelationsGirish, Uma / Raz, Ran / Zhan, Wei et al. | 2021
- 53
-
Fourier Growth of Structured 𝔽₂-Polynomials and ApplicationsBłasiok, Jarosław / Ivanov, Peter / Jin, Yaonan / Lee, Chin Ho / Servedio, Rocco A. / Viola, Emanuele et al. | 2021
- 54
-
Candidate Tree Codes via Pascal Determinant CubesBen Yaacov, Inbar / Cohen, Gil / Narayanan, Anand Kumar et al. | 2021
- 55
-
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear TimeBiswas, Amartya Shankha / Eden, Talya / Rubinfeld, Ronitt et al. | 2021
- 56
-
Ideal-Theoretic Explanation of Capacity-Achieving DecodingBhandari, Siddharth / Harsha, Prahladh / Kumar, Mrinal / Sudan, Madhu et al. | 2021
- 57
-
Visible Rank and Codes with LocalityAlrabiah, Omar / Guruswami, Venkatesan et al. | 2021
- 58
-
Pseudorandom Generators for Read-Once Monotone Branching ProgramsDoron, Dean / Meka, Raghu / Reingold, Omer / Tal, Avishay / Vadhan, Salil et al. | 2021
- 59
-
On the Power of Choice for k-Colorability of Random GraphsDani, Varsha / Gupta, Diksha / Hayes, Thomas P. et al. | 2021
- 60
-
Memory-Sample Lower Bounds for Learning Parity with NoiseGarg, Sumegha / Kothari, Pravesh K. / Liu, Pengda / Raz, Ran et al. | 2021
- 61
-
Testing Hamiltonicity (And Other Problems) in Minor-Free GraphsLevi, Reut / Shoshan, Nadav et al. | 2021
- 62
-
Parallel Repetition for the GHZ Game: A Simpler ProofGirish, Uma / Holmgren, Justin / Mittal, Kunal / Raz, Ran / Zhan, Wei et al. | 2021